Trails and Edge Reuse

Walks, Trails and Paths

A vertex sequence can travel through a graph in different ways. It may reuse an edge, or it may avoid reusing edges while still returning to a vertex it visited earlier. Keeping track of edges and vertices separately makes these possibilities easier to distinguish. In this tutorial, graphs are finite, simple and undirected, so an edge \(uv\) has endpoints \(u\) and \(v\), and traversing it from \(u\) to \(v\) or from \(v\) to \(u\) uses the same edge.

A walk is allowed to revisit vertices and to traverse the same edge more than once. A trail is a walk that does not traverse any edge more than once. The order in which edges are traversed still matters when describing the sequence, but an undirected edge and its reverse traversal count as the same edge. A path is a walk in which no vertex is repeated. A length-zero walk is a path, since its single vertex occurs only once.

These definitions impose different checks. First, each consecutive pair must be adjacent, or the sequence is not a walk at all. If it is a walk, compare its traversed edges: a repeated edge makes it not a trail. Then compare its vertices: a repeated vertex makes it not a path. Since a path has distinct vertices, it cannot repeat an edge; hence every path is a trail. The reverse implication fails: a trail can revisit a vertex without reusing an edge.

Testing a Sequence Systematically

For an undirected graph, record each traversed edge as an unordered pair. Thus the steps \(u\) to \(v\) and \(v\) to \(u\) both use the edge \(uv\). A reliable classification checks the sequence in this order:

1. Check every consecutive pair against \(E\). If one is absent, the sequence is not a walk.
2. If it is a walk, list the traversed edges in order and check whether any edge occurs more than once. This decides whether it is a trail.
3. Check the vertex list for repetition. If none occurs, the walk is a path; if a vertex repeats, it is not a path.

This order avoids a common confusion: finding a repeated vertex does not by itself show that a walk is not a trail. The repeated visit might use different edges on the two occasions. Conversely, seeing different directions of travel does not make a repeated edge new. The classification depends on the edges of the graph, not on how the written sequence looks.

Results About Trails

Proof. Let \(v_0,v_1,\ldots,v_k\) be a path, so all its vertices are distinct. If two traversed edges were the same undirected edge, then for some indices \(i\ne j\), the unordered pairs \(\{v_{i-1},v_i\}\) and \(\{v_{j-1},v_j\}\) would be equal. Because the graph has no loops and the vertices of the path are distinct, each vertex in the sequence occurs at only one position. The equality of those unordered pairs would therefore require the same pair of positions, so \(i=j\), a contradiction. Thus no edge repeats, and the path is a trail. To see that a trail need not be a path, the sequence \(1,2,3,1,5\) in the preceding example is a trail but repeats vertex \(1\). \(\square\)

For a trail, the length counts the distinct edges it traverses. This gives a bound that is useful even when the graph has isolated vertices or no edges at all.

Proof. Consider a trail of length \(k\). By definition, its \(k\) traversed edges are distinct members of \(E\), so \(k\le |E|=m\). If \(k=m\), the trail uses \(m\) distinct edges from a set of \(m\) edges; its edge set must therefore be all of \(E\). Conversely, if the trail traverses every edge, it traverses each at most once by the definition of a trail, so it traverses each of the \(m\) edges exactly once and has length \(m\). This also covers \(m=0\): a length-zero trail traverses every edge of an edgeless graph, since there are none. \(\square\)

The proposition concerns the number of distinct edges used, not the number of vertices visited. A trail may have more steps than vertices if it revisits vertices; it still cannot have more steps than there are edges. Nor does the bound say that a trail of length \(m\) exists in every graph. It says that if a trail has that length, it has used every edge.

Classifying Several Sequences

Common Mistakes

Mistake: treating a repeated vertex as a repeated edge. In the first sequence of the last example, vertex \(1\) is visited twice. That alone does not disqualify the sequence as a trail: its edge list is \(12,23,13,14\), with no repeated edge. The correction is to check edge repetition and vertex repetition separately.

Mistake: treating a reversed edge as new. In the sequence \(a,b,c,b\), the steps \(b\) to \(c\) and \(c\) to \(b\) are sometimes mistakenly recorded as two different edges. The graph is undirected, so both steps use the one edge \(bc\); the walk is not a trail.

Mistake: checking repetition before checking adjacency. A sequence with an absent consecutive pair is not a walk, even if no written vertex or edge appears twice. For \(1,4,2\), the missing edge \(42\) settles the classification before any trail or path test is needed.

These distinctions are useful whenever a problem asks how a sequence travels through a graph. A walk records adjacency and order; a trail adds the restriction against reusing edges; a path adds the restriction against revisiting vertices. Applying the tests in that order keeps each condition separate.