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.

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.

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.