# Chapter 6. Walks, Trails, and Paths # Chapter 6. Walks, Trails, and Paths Graphs describe connection. To use those connections, one must define what it means to move through a graph. The basic notions are **walk**, **trail**, and **path**. They are similar, but they impose different restrictions on repetition. A walk may repeat vertices and edges. A trail may repeat vertices but not edges. A path repeats neither vertices nor edges. These distinctions become important in connectivity, Eulerian graphs, Hamiltonian graphs, shortest paths, and graph algorithms. ## 6.1 Movement in a Graph Let $$ G = (V,E) $$ be an undirected graph. A movement through \(G\) begins at a vertex, follows an edge to another vertex, then may continue along another edge. For example, if $$ \{a,b\}, \{b,c\}, \{c,d\} \in E, $$ then one may move from \(a\) to \(d\) through the sequence $$ a,b,c,d. $$ This sequence records the vertices visited. Consecutive vertices must be adjacent. The graph does not need geometry. Movement means adjacency, not physical distance. ## 6.2 Walks A **walk** in a graph is a finite sequence of vertices $$ v_0, v_1, \ldots, v_k $$ such that each consecutive pair is joined by an edge: $$ \{v_{i-1},v_i\} \in E(G) $$ for every $$ 1 \leq i \leq k. $$ The integer \(k\) is the **length** of the walk. It counts edges used, not vertices listed. A walk of length \(0\) consists of a single vertex: $$ v_0. $$ Walks allow repetition. A walk may visit the same vertex several times. It may also use the same edge several times. For example, if \(\{a,b\}\) and \(\{b,c\}\) are edges, then $$ a,b,c,b,a $$ is a walk. It repeats \(b\), and it uses edges in both directions. ## 6.3 Endpoints of a Walk In the walk $$ v_0, v_1, \ldots, v_k, $$ the vertex \(v_0\) is the **initial vertex**, and \(v_k\) is the **terminal vertex**. The walk is said to go from \(v_0\) to \(v_k\). If \(v_0 = v_k\), then the walk is **closed**. If \(v_0 \ne v_k\), then the walk is **open**. For example, $$ a,b,c,a $$ is closed if all required edges exist. The walk starts and ends at \(a\). The walk $$ a,b,c,d $$ is open if \(a \ne d\). ## 6.4 Trails A **trail** is a walk in which no edge is repeated. Vertices may repeat in a trail, but edges may not. For example, suppose the edges $$ \{a,b\}, \{b,c\}, \{c,a\}, \{a,d\} $$ belong to a graph. Then $$ b,c,a,b $$ is a closed trail, provided the edges \(\{b,c\}\), \(\{c,a\}\), and \(\{a,b\}\) are distinct. It starts and ends at \(b\), and it uses no edge twice. The sequence $$ a,b,c,b $$ is not a trail if it uses the same edge \(\{b,c\}\) twice. Trails are central in Eulerian graph theory, where one asks whether a graph has a trail using every edge exactly once. ## 6.5 Paths A **path** is a walk in which no vertex is repeated. If $$ v_0, v_1, \ldots, v_k $$ is a path, then the vertices $$ v_0, v_1, \ldots, v_k $$ are all distinct. Every path is a trail, because repeating an edge would force a repeated vertex. The converse need not hold. A trail may repeat a vertex without repeating an edge. For example, $$ a,b,c,d $$ is a path when all four vertices are distinct and consecutive vertices are adjacent. The sequence $$ a,b,c,a,d $$ is not a path because \(a\) appears twice. It may still be a trail if no edge is repeated. ## 6.6 Comparing Walks, Trails, and Paths The three notions form a hierarchy. | Object | Repeated vertices allowed | Repeated edges allowed | |---|---:|---:| | Walk | Yes | Yes | | Trail | Yes | No | | Path | No | No | Every path is a trail. Every trail is a walk. Thus $$ \text{path} \subseteq \text{trail} \subseteq \text{walk}. $$ The restrictions become stronger as one moves from walk to trail to path. A walk is the most flexible object. A path is the most restrictive. ## 6.7 Length The **length** of a walk, trail, or path is the number of edges used. If a vertex sequence has the form $$ v_0, v_1, \ldots, v_k, $$ then its length is $$ k. $$ It contains \(k+1\) vertex entries. For example, $$ a,b,c,d $$ has length \(3\), because it uses three edges: $$ \{a,b\}, \{b,c\}, \{c,d\}. $$ Length is important in distance, shortest paths, graph diameter, and algorithmic search. ## 6.8 Distance If two vertices \(u\) and \(v\) are connected by at least one path, the **distance** from \(u\) to \(v\) is the length of a shortest path between them. It is written as $$ d(u,v). $$ Thus $$ d(u,v)=\min\{\text{length}(P): P \text{ is a path from } u \text{ to } v\}. $$ If no path exists between \(u\) and \(v\), then the distance is often left undefined or taken to be \(\infty\), depending on convention. In an unweighted graph, every edge has length \(1\). In a weighted graph, distance usually means minimum total weight, not minimum number of edges. ## 6.9 Geodesics A shortest path between two vertices is sometimes called a **geodesic**. If $$ d(u,v)=k, $$ then any path from \(u\) to \(v\) of length \(k\) is a geodesic. There may be more than one geodesic between the same pair of vertices. For example, in a square graph, two opposite vertices have two different shortest paths of length \(2\). Geodesics describe efficient movement through a graph. They also define metric properties such as eccentricity, radius, center, and diameter. ## 6.10 Closed Walks A walk is closed if its first and last vertices are equal. A closed walk has the form $$ v_0, v_1, \ldots, v_k $$ with $$ v_0 = v_k. $$ For example, $$ a,b,c,a $$ is a closed walk if the edges \(\{a,b\}\), \(\{b,c\}\), and \(\{c,a\}\) exist. Closed walks may repeat vertices and edges. They are useful in matrix methods because powers of the adjacency matrix count walks, including closed walks. ## 6.11 Circuits A **circuit** is commonly used to mean a closed trail: a closed walk with no repeated edges. Thus a circuit starts and ends at the same vertex and uses each edge in the sequence at most once. For example, $$ a,b,c,d,a $$ is a circuit if all four edges exist and are distinct. Terminology varies. Some authors use circuit and cycle differently; others use them almost interchangeably. In this book, a circuit is a closed trail, while a cycle is a closed path with no repeated vertices except the first and last. ## 6.12 Cycles A **cycle** is a closed path. More explicitly, a cycle is a sequence $$ v_0, v_1, \ldots, v_k, v_0 $$ where $$ k \geq 2, $$ the vertices $$ v_0, v_1, \ldots, v_k $$ are distinct, and each consecutive pair is adjacent. A cycle of length \(k+1\) has \(k+1\) edges. For example, $$ a,b,c,a $$ is a cycle of length \(3\). It is also called a triangle. Cycles are fundamental because they measure circular structure. Trees are exactly the connected graphs with no cycles. ## 6.13 Path Graphs A **path graph** is a graph whose vertices can be arranged in one line so that consecutive vertices are adjacent and no other edges appear. The path graph on \(n\) vertices is denoted by $$ P_n. $$ It has $$ n $$ vertices and $$ n-1 $$ edges. For example, \(P_4\) has vertex sequence $$ v_1,v_2,v_3,v_4 $$ and edge set $$ \{\{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_4\}\}. $$ A path graph is itself a graph. A path inside a larger graph is a subgraph that has this form. ## 6.14 Walks in Directed Graphs In a directed graph, a walk must follow edge directions. A directed walk is a sequence $$ v_0, v_1, \ldots, v_k $$ such that $$ (v_{i-1},v_i) \in A(G) $$ for every $$ 1 \leq i \leq k. $$ The arc must go from the current vertex to the next vertex. For example, if $$ (a,b), (b,c), (c,d) $$ are arcs, then $$ a,b,c,d $$ is a directed walk. But if the graph contains \((b,a)\) instead of \((a,b)\), then one cannot move from \(a\) to \(b\) along that arc. Direction makes reachability asymmetric. ## 6.15 Directed Paths and Directed Cycles A **directed path** is a directed walk with no repeated vertices. A **directed cycle** is a closed directed path. For example, $$ a,b,c,a $$ is a directed cycle if the arcs $$ (a,b), (b,c), (c,a) $$ all exist. Directed cycles are important in dependency graphs. If tasks are represented by vertices and an arc \(u \to v\) means that \(u\) must precede \(v\), then a directed cycle represents a circular dependency. A directed graph with no directed cycles is called a directed acyclic graph, or DAG. ## 6.16 Reachability A vertex \(v\) is **reachable** from a vertex \(u\) if there exists a path from \(u\) to \(v\). In an undirected graph, reachability is symmetric. If \(v\) is reachable from \(u\), then \(u\) is reachable from \(v\). In a directed graph, reachability may be asymmetric. There may be a directed path from \(u\) to \(v\) but no directed path from \(v\) to \(u\). Reachability is the basic relation behind connected components, strongly connected components, traversal algorithms, and transitive closure. ## 6.17 Removing Repetition from a Walk Every walk from \(u\) to \(v\) contains a path from \(u\) to \(v\). This is a basic but important fact. If a walk repeats a vertex, the closed portion between the two appearances can be removed. Repeating this process eventually gives a walk with no repeated vertices, hence a path. For example, $$ a,b,c,d,b,e $$ contains the repeated vertex \(b\). Remove the closed portion $$ b,c,d,b. $$ The remaining sequence is $$ a,b,e, $$ provided the original walk included the edge \(\{b,e\}\). This is shorter and has the same endpoints. This principle shows that for reachability questions, walks and paths are equivalent: if a walk exists, then a path exists. ## 6.18 Example Let $$ V=\{a,b,c,d,e\} $$ and $$ E=\{\{a,b\},\{b,c\},\{c,d\},\{d,b\},\{d,e\}\}. $$ The sequence $$ a,b,c,d,b,c $$ is a walk. It repeats the edge \(\{b,c\}\), so it is not a trail. The sequence $$ a,b,c,d,b $$ is a trail. It uses the edges $$ \{a,b\},\{b,c\},\{c,d\},\{d,b\} $$ once each. It repeats the vertex \(b\), so it is not a path. The sequence $$ a,b,c,d,e $$ is a path. It has no repeated vertices. The sequence $$ b,c,d,b $$ is a cycle of length \(3\), because it returns to \(b\) and repeats no other vertex. ## 6.19 Summary A walk is a sequence of adjacent vertices. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices. A closed walk starts and ends at the same vertex. A circuit is a closed trail. A cycle is a closed path. These definitions describe movement in a graph. They are the basis for reachability, connectedness, distance, shortest paths, Eulerian trails, Hamiltonian paths, and many graph algorithms.