EF Walks, trails, and paths

Section 15.2 Walks, trails, and paths

Suppose

G = (V, E)

is a graph.

🔗

walk: 🔗
a finite sequence $v_{0}, e_{1}, v_{1}, e_{2}, \dots, v_{n - 1}, e_{n}, v_{n}$ of elements from $V \cup E,$ with each $v_{i} \in V$ and each $e_{i} \in E,$ such that edge $e_{i}$ connects vertices $v_{i - 1}$ and $v_{i}$
closed walk: 🔗
a walk that ends at the same vertex at which it started (that is, $v_{n} = v_{0}$ )
open walk: 🔗
a walk that isn’t closed (that is, $v_{n} \neq v_{0}$ )
trail: 🔗
a walk that traverses no edge more than once
path: 🔗
a walk that passes through no vertex more than once, except possibly the endpoints $v_{0}, v_{n}$

🔗

Note 15.2.1.

🔗

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

🔗

Example 15.2.2.

🔗

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 .$
🔗
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 15.2.3. Paths and trails.

🔗

Consider the following graph.

A graph to illustrate paths and trails — Figure 15.2.4. 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};$
- 🔗
  $v_{1}, e_{1}, v_{2}, e_{1}, v_{1};$
- 🔗
  $v_{2}, e_{1}, v_{1}, e_{1}, v_{2};$
🔗
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.

🔗

Worked Example 15.2.5.

🔗

Consider again the graph in Figure 15.2.4 from Example 15.2.3. How many trails from

v_{3}

v_{4}

exist? How many of those trails are paths? Are there any paths from

v_{3}

v_{4}

that are not trails?

Solution.

We can solve this using a graph! The graph in Figure 15.2.6 was created by mapping out all possible trails starting at

v_{3}

and ending at

v_{4},

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.

Counting all the nodes in the graph of Figure 15.2.6 that are labelled with a walk that ends in

v_{4},

we see that there are ten trails from

v_{3}

v_{4} .

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}

v_{4},

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.)

From the result in Figure 15.2.7, we see that there are only three paths from

v_{3}

v_{4},

and each of them is a trail.

A graph to map the possible trails in another graph. — Figure 15.2.6. Mapping the trails from $v_{3}$ to $v_{4}$ in the graph of Figure 15.2.4.

A graph to map the possible paths in another graph. — Figure 15.2.7. Mapping the paths from $v_{3}$ to $v_{4}$ in the graph of Figure 15.2.4.

🔗

Proposition 15.2.8.

🔗

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^{'}} .

Initially, there are two possibilities to consider. If each of the two assumed traversals of

e

moves from

v

v^{'},

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

v^{'}

and

v^{'}

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 15.2.9.

🔗

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

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 15.2 Walks, trails, and paths

Note 15.2.1.

Example 15.2.2.

Example 15.2.3. Paths and trails.

Worked Example 15.2.5.

Proposition 15.2.8.

Proof.

Case $e$ is a loop.

Case $e$ is not a loop.

Note 15.2.9.

Section 15.2 Walks, trails, and paths

Note 15.2.1.

Example 15.2.2.

Example 15.2.3. Paths and trails.

Worked Example 15.2.5.

Proposition 15.2.8.

Proof.

Case e is a loop.

Case e is not a loop.

Note 15.2.9.

Case $e$ is a loop.

Case $e$ is not a loop.