Walk in a graph Created 2026-10-06 Updated 2026-10-14
A walk records a journey through a graph as a finite alternating sequence
where each edge joins the consecutive vertices and . Both vertices and edges may repeat. Its length is , 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.[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.[ref]
We allow the zero-length walk at every vertex . 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.[ref]
Use the same constructed graph throughout these three sections:
Here denotes the unordered pair , and . Two triangles in a graph, and , share , with one extra edge . 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.
Figure 1.
One constructed graph: repeated edges in a walk, repeated vertices in a trail, and a graph path
. Details.
The length-six walk uses and twice, so it is not a trail. The length-six trail returns to but uses six different edges, so it is not a graph path. The length-three graph path repeats neither vertices nor edges. Thus
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 to contains a graph path from to after deleting detours. For a proof outline, if with , 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 . 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.[ref]
Why the 2-core is unique 2026-10-18
Suppose is any vertex set whose induced subgraph has every degree of a vertex at least two. No vertex of can be the first one deleted from : before such a deletion it still has its two graph neighbours within , contradicting eligibility for deletion. Consequently every qualifying survives every legal deletion sequence. Once deletion stops, its remainder itself qualifies, because every surviving vertex has at least two surviving graph neighbours. Therefore for every qualifying : is the unique maximum and the final remainder is independent of deletion order. The intermediate FIFO queues and deletion orders can differ.
There is also a direct existence argument. If and qualify, then qualifies: each vertex retains at least the two graph neighbours it already had in or in . Taking the union of all qualifying vertex sets produces the maximum. This rules out a collection of competing, incomparable inclusion-maximal answers. It also explains why restricting the search to connected subgraphs would change the question.