One Sequence, Several Different Restrictions
The words walk, trail, path and cycle describe different features of a sequence of adjacent vertices. The main distinction is what the sequence is allowed to repeat. In particular, a repeated vertex is not the same thing as a repeated edge: a sequence can revisit a vertex while using a new edge each time.
Throughout, graphs are finite, simple and undirected. A vertex sequence \(v_0,v_1,\ldots,v_\ell\) specifies a traversal only if every consecutive pair \(v_{i-1},v_i\) is an edge. Its length is the number \(\ell\) of traversed edges. The edge used at step \(i\) is \(v_{i-1}v_i\); because the graph is undirected, \(uv\) and \(vu\) refer to the same edge.
A length-zero sequence consisting of one vertex is a walk, trail and path; it is not a cycle. A path has distinct vertices, so its first and last vertices differ when its length is positive. A cycle is different: its first vertex is repeated as the final vertex, and its other vertices are distinct. In a simple graph there are no loops, so a closed sequence of length one is impossible. A closed sequence of length two traverses one edge out and back, and therefore is not a cycle.
What the Restrictions Imply
Paths and trails both satisfy the definition of a walk, but they impose different extra restrictions. A path forbids repeated vertices. A trail forbids repeated edges. The distinction matters because edges can be revisited only by revisiting vertices, but revisiting a vertex does not force any edge to be reused.
Proof. First suppose a path repeats an edge at steps \(i\) and \(j\), where \(i<j\). The edge at step \(i\) has endpoints \(v_{i-1},v_i\), and the edge at step \(j\) has endpoints \(v_{j-1},v_j\). Since the graph is undirected and simple, equality of these edges means either \(v_{i-1}=v_{j-1}\) and \(v_i=v_j\), or \(v_{i-1}=v_j\) and \(v_i=v_{j-1}\). In either case, two positions in the vertex sequence have the same vertex. This contradicts the definition of a path. Thus a path has no repeated edge and is a trail.
Now suppose a walk repeats an edge at steps \(i<j\). The same endpoint alternatives apply. In either alternative, at least one vertex occurs at two positions in the sequence. Hence repeating an edge forces a repeated vertex. The converse does not follow: a walk may visit a vertex again using different incident edges. Such a walk can be a trail without being a path. \(\square\)
A cycle is a closed trail as well as a closed walk: its edges cannot repeat because its vertices, apart from the matching first and last vertex, are distinct. But a closed trail need not be a cycle. It may revisit a vertex other than just the required return to its start. The definitions therefore form a useful checklist, not a single interchangeable list of names.
| Type | Must be adjacent at every step? | May repeat vertices? | May repeat edges? | Must be closed? |
|---|---|---|---|---|
| Walk | Yes | Yes | Yes | No |
| Trail | Yes | Yes | No | No |
| Path | Yes | No | No | No, except the length-zero case has the same start and end |
| Cycle | Yes | Only the start vertex is repeated at the end | No | Yes |
Classifying Sequences Carefully
Worked Example: A Path and a Cycle in One Graph
Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,cd\}\). Classify the sequences \(a,b,c,d\) and \(a,b,c,a\).
For \(a,b,c,d\), check each consecutive pair: \(ab\in E\), \(bc\in E\), and \(cd\in E\). The sequence has length \(3\), and its traversed edge sequence is \(ab,bc,cd\). Its vertices \(a,b,c,d\) are all distinct, so it is a path. Since it has no repeated edge, it is also a trail; and every path or trail is a walk by definition. Its endpoints are \(a\) and \(d\), which differ, so it is open.
For \(a,b,c,a\), the consecutive pairs give edges \(ab,bc,ca\), all of which belong to \(E\). The sequence has length \(3\), begins and ends at \(a\), and has distinct vertices \(a,b,c\) before returning to \(a\). It is therefore a cycle. It is also a closed trail and a closed walk.
Check: the first sequence uses the three listed edges \(ab,bc,cd\) once each and never repeats a vertex. The second uses \(ab,bc,ca\), which are three distinct edges, and its only repeated vertex is the required first-and-last \(a\). These checks match the path and cycle definitions.
Worked Example: A Closed Trail That Is Not a Cycle
Let \(G=(V,E)\) have \(V=\{x,a,b,c,d\}\) and \(E=\{xa,ab,bx,xc,cd,dx\}\). Classify the sequence \(x,a,b,x,c,d,x\).
Read the sequence one step at a time. The traversed edges are \(xa\), \(ab\), \(bx\), \(xc\), \(cd\), and \(dx\). Each belongs to \(E\), so the sequence is a walk of length \(6\). No edge occurs twice, so it is a trail. The first and last vertices are both \(x\), so it is closed.
The vertex \(x\) also occurs at an intermediate position, after the sequence \(x,a,b,x\). Thus the vertices before the final return are not all distinct, and this closed trail is not a cycle. In fact, the sequence goes around the triangle \(x,a,b,x\), then around \(x,c,d,x\), without repeating an edge.
Check: the edge list has six entries, matching the six steps, and those entries are exactly the six distinct edges of \(G\). The vertex \(x\) occurs three times in the full sequence, so the cycle condition fails even though the trail and closed conditions hold.
Worked Example: Revisiting a Vertex Without Reusing an Edge
Let \(G=(V,E)\) have \(V=\{x,a,b,c,d\}\) and \(E=\{xa,ab,bx,xc,cd,dx\}\). Classify the sequence \(a,x,c,d,x,b\).
The consecutive pairs give \(ax,xc,cd,dx,xb\). These are all edges of \(G\); here \(ax=xa\) and \(xb=bx\), since the graph is undirected. The sequence has length \(5\), starts at \(a\), and ends at \(b\), so it is open. Its edges \(xa,xc,cd,dx,bx\) are all distinct, which makes it a trail.
The vertex \(x\) occurs twice, once after \(a\) and once after \(d\). Therefore the sequence is not a path. It is not a cycle either: it is open, and its vertices are not distinct apart from any possible first-and-last match (there is no such match here). It remains a walk, because it is a trail.
Check: there are five consecutive pairs and five distinct traversed edges. The only repeated vertex is \(x\), while the endpoints \(a\) and \(b\) differ. Thus the sequence satisfies the trail restriction but fails the path and cycle restrictions.
Worked Example: Repeating an Edge in a Walk
Let \(G=(V,E)\) have \(V=\{a,b,c\}\) and \(E=\{ab,bc,ca\}\). Classify the sequence \(a,b,c,a,c\).
The consecutive pairs give \(ab,bc,ca,ac\), and each is an edge of \(G\). Since the graph is undirected, \(ac\) and \(ca\) denote the same edge. The sequence is a walk of length \(4\), but it traverses edge \(ac\) twice: first from \(c\) to \(a\), and then from \(a\) to \(c\). It is therefore not a trail and cannot be a path.
The first vertex is \(a\) and the last is \(c\), so the sequence is open. It is not a cycle, which must be closed. The repeated edge also causes repeated vertices: \(a\) occurs at positions \(0\) and \(3\), and \(c\) occurs at positions \(2\) and \(4\).
Check: the four steps use \(ab\), \(bc\), \(ca\), and \(ac=ca\). There are only three distinct edges in that list, so one edge has been repeated. This confirms that the sequence is a walk but not a trail.
A Reliable Classification Checklist
When a sequence is supplied, classify it from the definitions rather than from its appearance or its name. First check every consecutive pair against the edge set. If even one pair is not an edge, the sequence is not a walk, and therefore is not a trail, path or cycle. If it is a walk, record the edge traversed at every step, remembering that reversing an undirected edge does not make it a new edge.
For each \(i\) from \(1\) to \(\ell\), verify that \(v_{i-1}v_i\in E\). If any check fails, the sequence is not a walk.
Compare the traversed edges as undirected edges. If none repeats, the walk is a trail; if one repeats, it is only a walk.
If no vertex repeats, the walk is a path. Repeated vertices rule out a path, but do not by themselves rule out a trail.
For a cycle, the sequence must be closed, have length at least \(3\), and have distinct vertices before the final return to its starting vertex.
These checks explain a common mistake: “A repeated vertex means a repeated edge.” That statement is false. In the closed-trail example, the sequence \(x,a,b,x,c,d,x\) visits \(x\) several times but uses \(xa,ab,bx,xc,cd,dx\) exactly once each. The correction is to track the edge sequence separately from the vertex sequence. Repeating an edge does force a repeated vertex, as proved above; repeating a vertex does not force an edge to repeat.
Another mistake is to call every closed trail a cycle. The sequence in the closed-trail example starts and ends at \(x\), but it revisits \(x\) before its final return. A cycle permits only the start vertex to recur at the end; all vertices in between must be distinct. Closure alone is not enough.
These distinctions are useful whenever a graph argument asks for a route between vertices or a closed traversal. The required object may need only adjacency (a walk), may forbid edge reuse (a trail), may forbid vertex reuse (a path), or may require a particular closed form (a cycle). Checking precisely which restriction is needed prevents a valid sequence from being rejected—or an invalid one from being accepted.
Check Your Understanding
For each question, state which condition on vertices, edges or endpoints determines the answer.
- Can a trail repeat a vertex? Give a short explanation using the definition of a trail.
- In a simple undirected graph, why does traversing the same edge in opposite directions count as repeating an edge?
- A walk is closed and has length \(2\). Explain why it is not a cycle.
- Give a sequence that is a trail but not a path, and identify the repeated vertex and the distinct edges.
- What additional conditions distinguish a cycle from a closed trail?