Undirected Paths

Definition

Let $(V, E)$ be an undirected graph. An (undirected) path between vertex $v \in V$ and vertex $w \neq v$ is a finite sequence of distinct vertices, whose first coordinate is $v$ and whose last coordinate is $w$, and whose consecutive coordinates are adjacent in the graph. We call the first and last coordinate the endpoints of the path. We say the path is between its endpoints.

The length of a path is one less than the number of vertices: namely, the number of edges. Notice that this definition disagrees with the definition of the “length” of the sequence of vertices (namely, the number of vertices). The length of a path is always at least one: there exists a path of length one between any two adjacent vertices. If a path has length two or greater, we call a vertex which is not the first or last vertex an interior vertex.

Two vertices are connected in a graph if there exists at least one path between them. A graph is connected if each pair of vertices is connected. Recall that two vertices are adjacent if they are connected by a path of length one. In contrast, two vertices are connected if they are connected by a path of any length. In other words, all adjacent vertices are connected.

A cycle is a sequence whose first and last coordinate are identical, all other coordinates are distinct, and consecutive coordinates are adjacent. An undirected graph is acyclic if there are no cycles of its vertices.

Other terminology

Some authors allow paths to contain repeated vertices, and call a path with distinct vertices a simple path. Similarly, some authors allow a cycle to contain repeated vertices, and call a path with distinct vertices a simple cycle or circuit. Some authors use the term loop instead of cycle.

A cycle which uses every vertex at least once is called a complete cycle (or—more often—Hamiltonian cycle, Hamiltonian circuit) Likewise, a path which uses every vertex at least once is called a complete path (or—more often—Hamiltonian path, traceable path).

Notation

Let $G = (V, E)$ be a graph. A path between $v$ and $w$ (with $v \neq w$) in $G$ is a sequence $(v_0, v_1, \dots , v_k)$ where $v_0 = v$ and $v_k = w$ and $\set{v_i, v_{i+1}} \in E$ for $i = 0, \dots , k-1$.