Turning Any Walk Into a Path

Why Repeated Vertices Can Be Removed

A walk can revisit vertices, sometimes many times, while still travelling between the same two endpoints. Each return to a vertex creates a closed portion of the walk: the part between two occurrences of that vertex. Removing that portion can make the route shorter without changing where it starts or ends. Repeating this operation gives a basic and useful fact: whenever a walk joins two vertices, there is also a path joining those same vertices.

Throughout, graphs are finite and simple. A walk of length \(\ell\) is a sequence \(v_0,v_1,\ldots,v_\ell\) in which every consecutive pair is adjacent. Vertices and edges may repeat in a walk. Its endpoints are \(v_0\) and \(v_\ell\). A walk is closed if its endpoints are equal. A path is a walk with no repeated vertices; a path of length zero, consisting of one vertex, is allowed.

The key detail is that a deletion removes a stretch of the sequence, not both copies of the repeated vertex. The retained copy is the point where the sequence before the deletion joins the sequence after it. Because the two occurrences name the same vertex, that join preserves adjacency.

The Deletion Procedure

Suppose a walk \(W=v_0,v_1,\ldots,v_\ell\) has a repeated vertex \(v_i=v_j\), where \(i<j\). If \(j<\ell\), replace \(W\) by the sequence

The proposed join is valid: \(v_i=v_j\), and \(v_j\) is adjacent to \(v_{j+1}\), so \(v_i\) is adjacent to \(v_{j+1}\) as well. All other consecutive pairs are unchanged. If \(j=\ell\), replace the walk by \(v_0,\ldots,v_i\). Its last vertex \(v_i\) equals the original last vertex \(v_\ell\). In either case, the first vertex is still \(v_0\), the last vertex is still \(v_\ell\), and the length decreases by \(j-i\), a positive integer.

This operation is repeated whenever a repeated vertex remains. The procedure cannot continue indefinitely: the length is a nonnegative integer and strictly decreases at every deletion. When no repeated vertex remains, the resulting walk is a path. If the original endpoints were the same, the resulting path may be the length-zero path at that vertex.

The Main Result

Proof. Let \(W=v_0,\ldots,v_\ell\) be the given walk, where \(v_0=u\) and \(v_\ell=v\). If no vertex repeats, \(W\) is already a path. Otherwise, choose two indices \(i<j\) with \(v_i=v_j\) and delete the closed subwalk between them as described above. The resulting sequence is still a walk: the only possible new consecutive pair is \(v_i,v_{j+1}\) when \(j<\ell\), and this pair is adjacent because \(v_i=v_j\) and \(v_jv_{j+1}\) was an edge. If \(j=\ell\), the shortened sequence ends at \(v_i=v_\ell=v\). Thus the endpoints remain \(u,v\) in both cases. The new length is the old length minus \(j-i\), which is strictly smaller because \(j-i\geq 1\). Each deletion therefore preserves the endpoints and decreases the nonnegative integer length. After finitely many deletions, no vertex repeats. The resulting walk is a path from \(u\) to \(v\). \(\square\)

The theorem also covers degenerate cases. A walk of length zero already has no repeated vertices and is a path. In particular, if its endpoints agree, the theorem promises a path from a vertex to itself, and the length-zero path satisfies that conclusion. If a positive-length walk starts and ends at the same vertex, the deletion process can remove the closed walk until it reaches that trivial path.

Proof. Assume at least one walk between the two fixed vertices exists. The set of lengths of such walks is a nonempty set of nonnegative integers, so it has a minimum. Let \(W\) be a walk of that minimum length. If \(W\) repeated a vertex, deleting the closed subwalk between two occurrences would give a walk with the same endpoints and strictly smaller length. That contradicts the choice of \(W\). Hence \(W\) has no repeated vertices and is a path. \(\square\)

Worked Deletions

Common Mistakes and What the Result Does Not Say

Mistake: removing both occurrences of a repeated vertex. In the first example, if we erase both copies of \(a\) from \(a,b,c,a,d,c\), we get \(b,c,d,c\). This sequence begins at \(b\), not \(a\), and so does not preserve the original endpoints. The correct deletion keeps one \(a\) and removes the closed subwalk between the two occurrences, leaving \(a,d,c\). The retained vertex is essential because it provides the valid point where the remaining sequence joins.

Mistake: assuming the shortcut uses a new edge. A deletion is valid not because every pair of vertices can be joined, but because the relevant repeated vertex is the same vertex at both positions. When \(j<\ell\), the edge \(v_jv_{j+1}\) already exists. Since \(v_i=v_j\), that same edge joins \(v_i\) to \(v_{j+1}\). No edge outside the original graph is added.

Mistake: expecting a unique answer. Different choices of repeated occurrences can leave different paths, as the first example shows. The conclusion is existence of a path with the same endpoints; it does not prescribe which path the deletions must produce.

The result concerns a walk that is already given. It does not claim that every pair of vertices in a graph has such a walk. If no walk between two vertices is available, there is nothing to shorten. When a walk is available, the theorem shows that repeated detours are not needed to retain its endpoints.