15.2: Walks, trails, and paths

Last updated
Save as PDF

Page ID: 83479

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Suppose \(G = (V,E)\) is a graph.

Definition: Walk

a finite sequence \(v_0, e_1, v_1, e_2, \ldots, v_{n - 1}, e_n, v_n\) of elements from \(V \cup E\text{,}\) with each \(v_i \in V\) and each \(e_i \in E\text{,}\) such that edge \(e_i\) connects vertices \(v_{i-1}\) and \(v_i\)

Definition: Closed Walk

a walk that ends at the same vertex at which it started (that is, \(v_n = v_0\))

Definition: Open Walk

a walk that isn't closed (that is, \(v_n \neq v_0\))

Definition: Trail

a walk that traverses no edge more than once

Definition: Path

a walk that passes through no vertex more than once, except possibly the endpoints \(v_0,v_n\)

Note \(\PageIndex{1}\)

We may also apply the adjectives open and closed to trails and paths.

Example \(\PageIndex{1}\)

Consider the graph in Example 15.1.1.

The “trip” we found in the example is a trail of maximal length starting at vertex \(C\text{.}\)
The walks \(C,r_1,R,r_4,D\) and \(C,r_1,R,r_2,C\) are both paths, the first open and the second closed.
The walk \(C,r_1,R,r_4,D,r_4,R\) is neither a path nor a trail.

Example \(\PageIndex{2}\): Paths and Trails

Consider the following graph.

Figure \(\PageIndex{1}\): A example graph to illustrate paths and trails.

This graph has the following properties.

Every path or trail passing through \(v_1\) must start or end there but cannot be closed, except for the closed paths:

\(v_1\text{;}\)
\(v_1, e_1, v_2, e_1, v_1\text{;}\)
\(v_2, e_1, v_1, e_1, v_2\text{;}\)

Walk \(v_1, e_1, v_2, e_5, v_3, e_4, v_4,\) is both a trail and a path.
Walk \(v_1, e_1, v_2, e_5, v_3, e_6, v_3, e_4, v_4,\) is a trail but not a path.

Example \(\PageIndex{3}\)

Consider again the graph in Figure \(\PageIndex{1}\) from Example \(\PageIndex{2}\). How many trails from \(v_3\) to \(v_4\) exist? How many of those trails are paths? Are there any paths from \(v_3\) to \(v_4\) that are not trails?

Solution

We can solve this using a graph! The graph in Figure \(\PageIndex{1}\) was created by mapping out all possible trails starting at \(v_3\) and ending at \(v_4\text{,}\) moving across one edge at a time. Each node in this new (directed) graph is labelled with a partial walk that is a continuation of the walk assigned to the node above it. Each leg in the graph stops when the associated walk being followed reaches \(v_4\) and cannot be continued without repeating another edge. To save space in the node labels, we have used “…” to mean the walk from the previous node.

Figure \(\PageIndex{2}\): Mapping the trails from \(v_3\) to \(v_4\) in the graph of Figure \(\PageIndex{1}\).

Counting all the nodes in the graph of Figure \(\PageIndex{2}\) that are labelled with a walk that ends in \(v_4\text{,}\) we see that there are ten trails from \(v_3\) to \(v_4\text{.}\) Also, we can easily see that only three of the trails are paths.

We can use the same technique to map out all paths from \(v_3\) to \(v_4\text{,}\) but this time we terminate a leg when we cannot move off a vertex without repeating a vertex that is already visited in that walk. (Note that the walk \(v_3,e_6,v_3\) is a path, but if we extend this walk in any way it will no longer be a path.)

Figure \(\PageIndex{3}\): Mapping the paths from \(v_3\) to \(v_4\) in the graph of Figure \(\PageIndex{1}\).

So there are only three paths from \(v_3\) to \(v_4\text{,}\) and each of them is a trail.

Proposition \(\PageIndex{1}\)

Every open path is a trail.

Proof

We will prove the contrapositive: a walk that is not a trail cannot be an open path. So suppose \(W\) is a walk in a graph, and that \(W\) traverses edge \(e\) twice.

Case \(e\) is a loop.
Then \(W\) passes through the vertex incident to \(e\) at least three times, hence is not a path.

Case \(e\) is not a loop.
Write \(e=\{v,v'\}\text{.}\) Initially, there are two possibilities to consider. If each of the two assumed traversals of \(e\) moves from \(v\) to \(v'\text{,}\) then \(W\) passes through each of \(v,v'\) at least twice, and hence is not a path. If the two assumed traversals of \(e\) move \(v\) to \(v'\) and \(v'\) to \(v\) respectively, then \(W\) passes through \(v\) at least twice. If \(W\) traverses \(v\) twice because it both starts and ends there, then \(W\) is not open. If \(W\) is open and traverses \(v\) twice, then \(W\) is not a path. So in any case, \(W\) is not an open path.

Note \(\PageIndex{2}\)

In Activity 15.1, you are asked to create counterexamples of some statements related to the above proposition.