Paths

In a graph, a path is a sequence of vertices $(v_1, v_2, ..., v_k)$ such that each consecutive pair $(v_i, v_{i+1})$ is connected by an edge. The path has length $k-1$ (the number of edges used). Paths can be simple (no repeated vertices) or may allow repeated vertices and edges, depending on the context.

Important properties

• A path connects two vertices by a sequence of edges.

• A simple path does not repeat any vertex.

• The length of a path is the number of edges it uses.

• If a path starts and ends at the same vertex, it is called a cycle (if it has at least one edge).