= Walk in a graph
{title2=$v_0,e_1,v_1,\ldots,e_m,v_m$}
= Walk
{synonym}
A <walk> records a journey through a <graph> as a finite alternating <sequence>
$$
W=(v_0,e_1,v_1,\ldots,e_m,v_m),\qquad m\geq0,
$$
where each <edge> $e_i$ joins the consecutive <vertices> $v_{i-1}$ and $v_i$. Both <vertices> and <edges> may repeat. Its length is $m$, counting <edge> traversals with repetitions, rather than counting different <edges> or measuring the drawing. Here a <graph path> means a <walk> with no repeated <vertices>; a <trail> instead forbids repeated <edges>. These conventions distinguish a journey's record from the <subgraph> consisting of the connections it used.https://ptwiddle.github.io/MAS341-Graph-Theory-2017/lecturenotes/lecture3.html[Paul Johnson, MAS341, Lecture 3: walks and trails]{ref}
Unless stated otherwise, the examples below use a finite <simple graph> that is an <undirected graph>, so an <edge> may be traversed in either direction. In a <multigraph>, retain each <edge>'s individual identity as well as its endpoint <vertices>: two parallel <edges> are different choices for the same step. If <self-loops> are allowed, traversing one leaves the current <vertex> unchanged but adds one to the length. In a <directed graph>, each step must follow its <directed edge> from its initial to its terminal <vertex>, giving a <directed walk>; reversing a journey need not be possible.https://people.math.binghamton.edu/zaslav/Oldcourses/581.S99/notes.html[Thomas Zaslavsky, Supplementary Notes for Graduate Graph Theory: edge identities and walks]{ref}
We allow the zero-length <walk> $(v)$ at every <vertex> $v$. It uses no <edges>, so it is also a <trail> and a <graph path>, and its coinciding endpoints make it a <closed walk>. This means staying put is a legitimate journey; a <graph> with no <vertices> has no such <walk>. Positive-length restrictions will be stated explicitly.<Mathematics for Computer Science by Eric Lehman and others>[Lehman, Leighton and Meyer, Mathematics for Computer Science, §11.8.1: length-zero convention]{ref}
Use the same constructed <graph> throughout these three sections:
$$
V=\{A,B,C,D,E,F\},\qquad E=\{AB,BC,CA,AD,DE,EA,AF\}.
$$
Here $AB$ denotes the <unordered pair> $\{A,B\}$, and $CA=AC$. Two <triangles in a graph>, $ABC$ and $ADE$, share $A$, with one extra <edge> $AF$. These are schematic connections, not measured roads; the highlighted connections in the diagram show which <edges> are used, while the numbered <sequence> records their order.
\Image[/walks-trails-closed-walks-route-comparison.png]
{title=One constructed <graph>: repeated <edges> in a <walk>, repeated <vertices> in a <trail>, and a <graph path>}
The length-six <walk> $B,C,A,B,C,A,F$ uses $BC$ and $CA$ twice, so it is not a <trail>. The length-six <trail> $B,C,A,D,E,A,F$ returns to $A$ but uses six different <edges>, so it is not a <graph path>. The length-three <graph path> $B,C,A,F$ repeats neither <vertices> nor <edges>. Thus
$$
\{\text{graph paths}\}\subsetneq\{\text{trails}\}\subsetneq\{\text{walks}\}
$$
for this particular <graph>. The restrictions answer different routing questions: revisiting a junction is harmless for many journeys, whereas reusing a serviced road segment can matter for an inspection route. Travel costs require a <weighted graph>; a <walk>'s cost adds the weight of each traversal, even when an <edge> is used again.
Every finite <walk> from $s$ to $t$ contains a <graph path> from $s$ to $t$ after deleting detours. For a proof outline, if $v_i=v_j$ with $i<j$, delete the intervening <closed walk>. The retained steps still meet at the same <vertex>, and the length strictly decreases. Repeating terminates with no repeated <vertices>, or with the zero-length <graph path> when $s=t$. This explains why <reachability> can be formulated using either <walks> or <graph paths>. With nonnegative <edge> weights, deletion also cannot increase cost, connecting the argument to the <shortest path problem>; with negative weights that cost conclusion fails.https://ptwiddle.github.io/MAS341-Graph-Theory-2017/lecturenotes/lecture3.html[Paul Johnson, MAS341, Lecture 3: deleting repeated-vertex detours]{ref}
Back to article page
