9.2: Walks and Paths

Picturing digraphs with points and arrows makes it natural to talk about following successive edges through the graph. For example, in the digraph of Figure 9.5, you might start at vertex 1, successively follow the edges from vertex 1 to vertex 2, from 2 to 4, from 4 to 12, and then from 12 to 12 twice (or as many times as you like). The sequence of edges followed in this way is called a walk through the graph. A path is a walk which never visits a vertex more than once. So following edges from 1 to 2 to 4 to 12 is a path, but it stops being a path if you go to 12 again.

The natural way to represent a walk is with the sequence of successive vertices it went through, in this case:

1 2 4 12 12 12.

However, it is conventional to represent a walk by an alternating sequence of successive vertices and edges, so this walk would formally be

\[\label{9.1} 1 \langle 1 \rightarrow 2 \rangle 2 \langle 2 \rightarrow 4 \rangle 4 \langle 4 \rightarrow 12 \rangle 12 \langle 12 \rightarrow 12 \rangle 12 \langle 12 \rightarrow 12 \rangle 12.\]

The redundancy of this definition is enough to make any computer scientist cringe, but it does make it easy to talk about how many times vertices and edges occur on the walk. Here is a formal definition:

Definition 9.2.1.

A walk in a digraph, \(G\), is an alternating sequence of vertices and edges that begins with a vertex, ends with a vertex, and such that for every edge \(\langle u \rightarrow v \rangle\) in the walk, vertex \(u\) is the element just before the edge, and vertex \(v\) is the next element after the edge.

So a walk, \(\textbf{v}\), is a sequence of the form

\[\nonumber \textbf{v} ::= v_0 \langle v_0 \rightarrow v_1 \rangle v_1 \langle v_1 \rightarrow v_2 \rangle v_2 \ldots \langle v_{k-1} \rightarrow v_k \rangle v_k\]

where \(v_i \rightarrow v_{i+1} \in E(G)\) for \(i \in [0..k)\). The walk is said to start at \(v_0\), to end at \(v_k\), and the length, \(\mid \textbf{v} \mid\), of the walk is defined to be \(k\).

The walk is a path iff all the \(v_i\)’s are different, that is, if \(i \neq j\), then \(v_i \neq v_j\).

A closed walk is a walk that begins and ends at the same vertex. A cycle is a positive length closed walk whose vertices are distinct except for the beginning and end vertices.

Note that a single vertex counts as a length zero path that begins and ends at itself. It also is a closed walk, but does not count as a cycle, since cycles by definition must have positive length. Length one cycles are possible when a node has an arrow leading back to itself. The graph in Figure 9.1 has none, but every vertex in the divisibility relation digraph of Figure 9.5 is in a length one cycle. Length one cycles are sometimes called self-loops.

Although a walk is officially an alternating sequence of vertices and edges, it is completely determined just by the sequence of successive vertices on it, or by the sequence of edges on it. We will describe walks in these ways whenever it’s convenient. For example, for the graph in Figure 9.1,

• \((a, b, d)\), or simply \(abd\), is a (vertex-sequence description of a) length two path,
• \((\langle a \rightarrow b \rangle, \langle b \rightarrow d \rangle)\), or simply \(\langle a \rightarrow b \rangle \langle b \rightarrow d \rangle\), is (an edge-sequence description of) the same length two path,
• \(abcbd\) is a length four walk,
• \(dcbcbd\) is a length five closed walk,
• \(bdcb\) is a length three cycle,
• \(\langle b \rightarrow c \rangle \langle c \rightarrow b \rangle\) is a length two cycle, and
• \(\langle c \rightarrow b \rangle \langle b \rightarrow a \rangle \langle a \rightarrow d \rangle\) is not a walk. A walk is not allowed to follow edges in the wrong direction.

If you walk for a while, stop for a rest at some vertex, and then continue walking, you have broken a walk into two parts. For example, stopping to rest after following two edges in the walk (9.1) through the divisibility graph breaks the walk into the first part of the walk

\[\label{9.2.1} 1 \langle 1 \rightarrow 2 \rangle 2 \langle 2 \rightarrow 4 \rangle 4\]

from 1 to 4, and the rest of the walk

\[\label{9.2.2} 4 \langle 4 \rightarrow 12 \rangle 12 \langle 12 \rightarrow 12 \rangle 12 \langle 12 \rightarrow 12 \rangle 12.\]

from 4 to 12, and we’ll say the whole walk (9.1) is the merge of the walks (9.2) and (9.3). In general, if a walk \(\textbf{f}\) ends with a vertex, \(v\), and a walk \(\textbf{r}\) starts with the same vertex, \(v\), we’ll say that their merge, \(\textbf{f} \hat{} \textbf{r}\), is the walk that starts with \(\textbf{f}\) and continues with \(\textbf{r}\). ¹ Two walks can only be merged if the first ends with the same vertex, \(v\), that the second one starts with. Sometimes it’s useful to name the node \(v\) where the walks merge; we’ll use the notation \(\textbf{f} \hat{v} \textbf{r}\) to describe the merge of a walk \(\textbf{f}\) that ends at \(v\) with a walk \(\textbf{r}\) that begins at \(v\).

A consequence of this definition is that

Lemma 9.2.2.

\[\nonumber |\textbf{f} \hat{} \textbf{r}| = |\textbf{f}| + |\textbf{r}|\]

In the next section we’ll get mileage out of walking this way.

Finding a Path

If you were trying to walk somewhere quickly, you’d know you were in trouble if you came to the same place twice. This is actually a basic theorem of graph theory.

Theorem \(\PageIndex{3}\)

The shortest walk from one vertex to another is a path.

Proof. If there is a walk from vertex \(u\) to another vertex \(v \neq u\), then by the Well Ordering Principle, there must be a minimum length walk \(\textbf{w}\) from \(u\) to \(v\). We claim \(\textbf{w}\) is a path.

To prove the claim, suppose to the contrary that \(\textbf{w}\) is not a path, meaning that some vertex \(x\) occurs twice on this walk. That is,

\[\nonumber \textbf{w} = \textbf{e} \hat{x} \textbf{f} \hat{x} \textbf{g}\]

for some walks \(\textbf{e}, \textbf{f}, \textbf{g}\) where the length of \(\textbf{f}\) is positive. But then “deleting” \(\textbf{f}\) yields a strictly shorter walk

\[\nonumber \textbf{e} \hat{x} \textbf{g}\]

from \(u\) to \(v\), contradicting the minimality b of \(\textbf{w}. \quad \blacksquare\)

Definition \(\PageIndex{4}\)

The distance, \(\text{dist}(u, v)\), in a graph from vertex \(u\) to vertex \(v\) is the length of a shortest path from \(u\) to \(v\).

As would be expected, this definition of distance satisfies:

Lemma 9.2.5. [The Triangle Inequality]

\[\nonumber \text{dist}(u, v) \leq \text{dist}(u, x) + \text{dist}(x, v)\]

for all vertices \(u, v, x\) with equality holding iff \(x\) is on a shortest path from \(u\) to \(v\).

Of course, you might expect this property to be true, but distance has a technical definition and its properties can’t be taken for granted. For example, unlike ordinary distance in space, the distance from \(u\) to \(v\) is typically different from the distance from \(v\) to \(u\). So, let’s prove the Triangle Inequality

Proof. To prove the inequality, suppose \(\textbf{f}\) is a shortest path from \(u\) to \(x\) and \(\textbf{r}\) is a shortest path from \(x\) to \(v\). Then by Lemma 9.2.2, \(\textbf{f} \hat{x} \textbf{r}\) is a walk of length \(\text{dist}(u, x) + \text{dist}(x, v)\) from \(u\) to \(v\), so this sum is an upper bound on the length of the shortest path from \(u\) to \(v\) by Theorem 9.2.3.

Proof of the “iff” is in Problem 9.3. \(\quad \blacksquare\)

Finally, the relationship between walks and paths extends to closed walks and cycles:

Lemma 9.2.6. The shortest positive length closed walk through a vertex is a cycle through that vertex.

The proof of Lemma 9.2.6 is essentially the same as for Theorem 9.2.3; see Problem 9.7.

¹It’s tempting to say the merge is the concatenation of the two walks, but that wouldn’t quite be right because if the walks were concatenated, the vertex \(v\) would appear twice in a row where the walks meet.