Walks Record a Sequence of Steps
A walk describes a succession of steps through a graph. At each step, the next vertex must be joined to the current vertex by an edge. Unlike a list of vertices with no specified order, a walk records the order in which the steps are taken. It also records the corresponding edges, so each step can be checked against the graph.
Throughout, graphs are finite and simple: they have no loops or multiple edges, and their edges are undirected. For an edge \(uv\), the vertices \(u\) and \(v\) are its endpoints. In a walk, we write the vertices as \(v_0,v_1,\ldots,v_\ell\), in order, and the edge for the step from \(v_{i-1}\) to \(v_i\) as \(e_i=v_{i-1}v_i\).
The two sequences can be displayed together as \(v_0,e_1,v_1,e_2,\ldots,e_\ell,v_\ell\). Since the graph is simple, the edge joining two given adjacent vertices is unique. Even so, displaying both sequences makes each step explicit and is useful for checking the walk. The order matters: the walk \(u,v,w\) takes its first step from \(u\) to \(v\), then its second from \(v\) to \(w\).
A walk may revisit a vertex, and an edge may appear more than once. The definition imposes only the condition that each listed edge joins the two consecutive vertices beside it. In particular, the word “walk” by itself does not require all the vertices or edges to be distinct. Length counts steps, not the number of different vertices or edges encountered.
Endpoints and Length
These labels depend only on the two endpoints. A walk can visit its initial vertex at some intermediate point and still be open if it ends at a different vertex. Conversely, a closed walk can visit other vertices more than once before returning to its starting vertex. Closed does not mean that the walk has no repeated vertices; it means exactly that the first and last vertices agree.
A walk of length \(\ell\) has \(\ell+1\) vertex entries, because the vertex sequence starts at \(v_0\) and gains one new entry after each of its \(\ell\) steps. This counts entries in the sequence, not necessarily distinct vertices. For example, if the sequence is \(a,b,a\), it has three vertex entries but only two distinct vertices.
Worked Example: An Open Walk That Repeats an Edge
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,14\}\). Consider the sequence \(1,12,2,23,3,23,2,12,1,14,4\).
Reading the sequence in alternating vertex-edge order gives the vertex sequence \(1,2,3,2,1,4\) and the edge sequence \(12,23,23,12,14\). Check each step: \(12\) joins \(1\) to \(2\); \(23\) joins \(2\) to \(3\); the next \(23\) joins \(3\) to \(2\); \(12\) joins \(2\) to \(1\); and \(14\) joins \(1\) to \(4\). Thus every consecutive pair is joined by the listed edge, so this is a walk in \(G\).
The edge sequence has five entries, so the walk has length \(5\). The vertex sequence has six entries, as expected from \(5+1=6\). Its initial endpoint is \(1\), and its terminal endpoint is \(4\), so it is open. The repeated appearances of \(2\) and of the edges \(12\) and \(23\) do not stop it from being a walk.
Check: Counting the transitions in \(1\to2\to3\to2\to1\to4\) gives \(1,2,3,4,5\), hence five steps. The first and last vertices are \(1\) and \(4\), which are different, confirming that the walk is open.
Worked Example: A Closed Walk with Repeated Vertices
Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd,da,ac\}\). Consider the sequence \(a,ab,b,bc,c,ac,a,ad,d,da,a\), where \(ad\) and \(da\) both denote the edge joining \(a\) and \(d\).
The vertex sequence is \(a,b,c,a,d,a\), and the edge sequence is \(ab,bc,ac,ad,da\). The five steps are valid: \(ab\) joins \(a\) to \(b\); \(bc\) joins \(b\) to \(c\); \(ac\) joins \(c\) to \(a\); \(ad\) joins \(a\) to \(d\); and \(da\) joins \(d\) to \(a\). Therefore, the length is \(5\), the number of edges listed. There are \(6\) vertex entries, in agreement with \(5+1=6\).
The initial and terminal vertices are both \(a\), so this walk is closed. The vertex \(a\) appears at the beginning, in the middle, and at the end. The definition permits these repetitions. The sequence must still be checked step by step: the fact that its endpoints agree does not by itself establish that it is a walk.
Check: The terminal entry is \(a\), equal to the initial entry \(a\), so the walk is closed. Its five listed edges give length \(5\), despite there being only four distinct vertices in the graph.
Worked Example: A Walk of Length Zero
Let \(G=(V,E)\) have \(V=\{p,q,r\}\) and \(E=\{pq\}\). The sequence consisting just of \(r\) is a walk: its vertex sequence is \(r\), and its edge sequence is empty. There are no consecutive vertices to check, so the step condition has no instances that could fail.
The edge sequence has zero entries, so the walk has length \(0\). Its initial and terminal endpoints are both \(r\), making it closed. The same graph also has the walk \(p,pq,q\): its one listed edge joins the two consecutive vertices, so its length is \(1\) and its endpoints \(p\) and \(q\) differ. This second walk is open.
Check: The length-zero walk has one vertex entry and no edge entries, so the vertex count is \(0+1=1\). For the walk from \(p\) to \(q\), the edge count is \(1\) and the vertex count is \(2=1+1\).
Basic Operations on Walks
Two useful facts follow directly from the definition: walks can be reversed in an undirected graph, and compatible walks can be joined end to end. These operations preserve the information needed to determine endpoints and length.
Proof. Write \(W\) as vertex sequence \(v_0,\ldots,v_\ell\) and edge sequence \(e_1,\ldots,e_\ell\). For each \(i\), \(e_i\) joins \(v_{i-1}\) and \(v_i\). In reverse order, the vertex sequence is \(v_\ell,v_{\ell-1},\ldots,v_0\), and the edge sequence is \(e_\ell,e_{\ell-1},\ldots,e_1\). Each reversed step still uses an edge joining its consecutive vertices, because the edges are undirected. There are still \(\ell\) edges, and the endpoints are \(v_\ell\) and \(v_0\). This also holds for \(\ell=0\): the sequence consists of the same single vertex and has no edges.
Now let \(W_1\) have length \(r\) and \(W_2\) have length \(s\), with the terminal endpoint of \(W_1\) equal to the initial endpoint of \(W_2\). List all the steps of \(W_1\) first, followed by all the steps of \(W_2\), identifying the shared endpoint as the join. Every consecutive pair in the resulting sequence is a consecutive pair from one of the original walks, so its listed edge joins that pair. The resulting edge sequence has \(r+s\) entries. This argument includes \(r=0\) or \(s=0\): a length-zero walk contributes a single endpoint and no steps. Thus the concatenated sequence is a walk of length \(r+s\). \(\square\)
Worked Example: Reversing and Joining Walks
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,14\}\). Take \(W_1\) to be \(1,12,2,23,3\), which has vertex sequence \(1,2,3\), edge sequence \(12,23\), and length \(2\). Take \(W_2\) to be \(3,34,4\), which has vertex sequence \(3,4\), edge sequence \(34\), and length \(1\).
The terminal endpoint of \(W_1\) and initial endpoint of \(W_2\) are both \(3\). Joining the sequences gives \(1,12,2,23,3,34,4\), with edge sequence \(12,23,34\). Each edge joins the consecutive vertices beside it, and the length is \(2+1=3\). The joined walk starts at \(1\) and ends at \(4\), so it is open.
Reversing the joined walk gives \(4,34,3,23,2,12,1\). The edges still join consecutive vertices, in the reverse order, and the edge count is \(3\). Its endpoints are \(4\) and \(1\). Check: Reversal preserves the three listed edges, and concatenation has \(2+1=3\) edges, as the proposition predicts.
Common Mistakes and Why Walks Matter
Mistake: counting vertex entries as the length. In the first worked example, a mistaken count might say the length is \(6\), because the vertex sequence \(1,2,3,2,1,4\) has six entries. The correction is to count steps, or equivalently edges: there are five listed edges, so the length is \(5\). The six vertex entries agree with the formula “length plus one.”
Mistake: deciding open or closed from a repeated vertex somewhere in the sequence. The first worked example visits vertex \(1\) again before ending at \(4\), but it is open because its endpoints are different. In the second example, it is closed because the initial and terminal vertices are both \(a\). To classify a walk, compare only its first and last vertices.
Walks are a basic way to describe movement through a graph. They make the sequence of steps precise, and their lengths let us compare how many steps different descriptions use. The distinction between the sequence itself and the set of vertices it visits is important: a walk can visit one vertex several times, so listing only the distinct vertices would lose the order and the number of steps. Later graph concepts impose additional conditions on walks; the definition here is the starting point against which those conditions can be stated.
Check Your Understanding
For each question, count the edges in the specified walk and compare its first and last vertices where relevant.
- In the graph with \(V=\{1,2,3\}\) and \(E=\{12,23,13\}\), is \(1,12,2,23,3\) open or closed? What is its length?
- In the graph with \(V=\{a,b,c\}\) and \(E=\{ab,bc,ac\}\), write the vertex and edge sequences for \(a,ab,b,bc,c,ac,a\). Is the walk open or closed?
- What is the length and endpoint classification of the walk consisting only of vertex \(x\), in a graph with vertex set \(\{x,y\}\) and no edges?
- Two walks have lengths \(4\) and \(3\), and the first ends where the second begins. What is the length of their concatenation, and why is it a walk?
- A walk has seven edge entries. How many vertex entries does its vertex sequence have? Explain why this count does not imply that it visits seven distinct vertices.