Walks, Paths, and Cycles

How many fundamentally different ways can you move through a graph? This simple question turns out to organize an enormous amount of graph theory. A traveler moving along edges from vertex to vertex might repeat streets, revisit intersections, or do neither. Each restriction produces a different combinatorial object with its own name and theory. Distinguishing walks, trails, paths, and cycles is not pedantic bookkeeping. It is the vocabulary that later lets us state precise theorems. These cover connectivity, Eulerian circuits, and Hamiltonian cycles, all without ambiguity. The big picture is a hierarchy of increasingly restrictive notions of "movement" through a graph. A walk is the most permissive: any sequence of adjacent vertices. There is no restriction at all on repetition. A trail forbids reusing edges. A path forbids reusing vertices, which automatically forbids reusing edges as well. Circuits and cycles are the closed versions of trails and paths. They are walks that return to their starting point. Each restriction rules out a class of pathological behavior. Examples include infinite backtracking, retracing the same street, or looping around a block twice. Each is exactly the right notion for a different theorem later on. Why does this matter? Many of the deepest classical theorems in graph theory concern precisely these objects. They ask which of these objects exist. Euler's theorem on the bridges of Königsberg is one example. It states the existence of a closed trail using every edge exactly once. The Traveling Salesman Problem and Hamiltonian cycle theory are about paths and cycles. These use every vertex exactly once. Connectivity itself is defined in terms of the existence of paths between vertices. None of these statements can even be phrased correctly. This is true without the careful distinctions this article establishes. This article gives the formal definitions. It proves the basic structural facts relating walks, trails, and paths. Most importantly: every walk between distinct vertices contains a path between them. It also works through nontrivial examples that expose common points of confusion. These particularly concern edge-repetition versus vertex-repetition. Also covered is the special handling of closed walks.

Key takeaways

A walk is a vertex-edge sequence with no repetition restrictions; a trail is a walk with no repeated edges; a path is a walk with no repeated vertices.
Closed versions get their own names: a closed walk that is a trail is a circuit; a closed walk that is a path (except for the shared start/end) is a cycle.
Every walk between two distinct vertices contains a path between the same two vertices — this is the key structural theorem of the article.
Path ⟹ trail ⟹ walk, and these implications are strict: trails need not be paths, and walks need not be trails.
Length is measured in edges traversed (with multiplicity for walks/trails), not in vertices visited.
Key idea: restricting how much repetition is allowed in a walk produces a strict hierarchy of objects, and the passage from "some walk exists" to "a path exists" is a genuine theorem, not a definition.

Where this lives today

The walk/trail/path/cycle hierarchy is the load-bearing vocabulary of essentially all of algorithmic graph theory. Breadth-first and depth-first search algorithms are, at their core, procedures for finding shortest paths and detecting cycles efficiently, relying on exactly the extraction principle proved above to guarantee that reachability (a walk exists) is equivalent to the existence of a path. In network routing and telecommunications, finding a path (not merely a walk) between two nodes is essential to avoid wasted bandwidth from revisiting the same link. In cryptography and coding theory, cycle structure in graphs underlies constructions of expander graphs and error-correcting codes. In chemistry and bioinformatics, Eulerian trails (from Eulerian Graphs and Circuits) model DNA sequencing via the reconstruction of genome fragments, while Hamiltonian cycles (from Hamiltonian Graphs) model the Traveling Salesman Problem central to logistics and operations research. In pure mathematics, the notion of connectivity — whether a path exists between every pair of vertices — is the entry point to the theory of Connectivity and Components, which itself underlies network reliability theory and the structure theory of graphs more broadly.

Ask the tutor: Can you show step-by-step how the excision algorithm turns a specific messy closed walk into an Eulerian circuit or a simple cycle?

G = (V, E)

Intuition

Picture a graph as a map of intersections (vertices) joined by roads (edges). A walk is what happens if you drive with no memory at all: you might drive down the same road five times, and pass through the same intersection over and over, perhaps even doing a small back-and-forth (which is only possible if the graph has parallel edges or you retrace a single edge, i.e., an edge $uv$ traversed and then immediately traversed back $v$ to $u$ ). A trail is a walk taken by someone who refuses to drive down any road twice — but who might still pass through the same intersection more than once, arriving from a different direction each time and leaving on a road not yet used. A path is the walk of someone with a much stronger constraint: never revisit any intersection at all, which forces every road used to be used only once as well. The closed variants matter because "returning home" is qualitatively different from "ending up somewhere new." A circuit is a round trip using no road twice (but possibly passing through some intersections more than once along the way, always excepting the shared start/end vertex which is visited exactly at the beginning and the end). A cycle is the cleanest round trip of all: it revisits no intersection at all except that the very last stop coincides with the very first. The picture below shows a single small graph together with a walk that repeats an edge, a trail in the same graph that reuses a vertex but not an edge, and a path that repeats nothing.

Figure

A walk, a trail, and a path in the same graph

The extraction principle

The single most important structural fact tying these definitions together is that repetition can always be removed: if you can get from $u$ to $v$ at all by any walk, however wasteful, you can get from $u$ to $v$ by a path. This is the content of the theorem below, and it is what makes "connectivity" (defined via paths) equivalent to "reachability" (naturally phrased via walks).

G = (V,E)

k

u \ne v

e_i = e_j

Worked examples

Example 1 (Distinguishing all three notions in one non-symmetric graph). Let $G$ have vertex set $\{a,b,c,d,e\}$ and edge set

E = \{ab, bc, cd, de, ea, bd\}

(so $G$ is a 5-cycle $a$ – $b$ – $c$ – $d$ – $e$ – $a$ with one extra chord $bd$ ). Consider the sequence

S = a, b, d, c, b, e, a.

Check adjacency: $ab, bd, dc, cb, be, ea$ are all edges of $G$ (note $dc = cd$ and $cb = bc$ are the same edges listed differently, which is fine — edges are unordered pairs). So $S$ is a walk of length $6$ .

Is $S$ a trail? Its edges in order are $ab, bd, dc, cb, be, ea$ . As a multiset these are $\{ab, bd, cd, bc, be, ea\}$ — all six are distinct edges of $G$ (recall $|E|=6$ ), so no edge repeats. Hence $S$ is a trail. Since it starts and ends at the same vertex $a$ , it is in fact a circuit, and since it uses every edge of $G$ exactly once, it is an Eulerian circuit (a notion developed further in Eulerian Graphs and Circuits).
Is $S$ a path? No: the vertex $b$ appears at position $1$ and again at position $4$ . So $S$ is a circuit but not a cycle in the strict sense (a cycle would require no interior vertex repetition at all, only start = end).
Extract a path from $a$ to $e$ using $S$ as raw material. The sub-walk of $S$ from $a$ to $e$ is $a, b, d, c, b, e$ — this has a repeated vertex ( $b$ at positions $1$ and $4$ ). Apply the excision from the proof: delete the segment strictly between the two occurrences of $b$ , i.e. delete " $d,c$ " and merge, giving $a, b, e$ . Check: $ab$ and $be$ are edges of $G$ , and $a,b,e$ are pairwise distinct. So $a,b,e$ is a path from $a$ to $e$ of length $2$ , exactly as the extraction theorem guarantees, and indeed it is even a shortest $a$ – $e$ walk (length 2, since $a$ and $e$ are not adjacent... wait, they are adjacent via edge $ea$ ! Let's recheck: $ea \in E$ , so the walk $a,e$ of length $1$ exists and is shorter). This shows the extracted path need not be a shortest path — extraction guarantees a path, not the shortest one. The genuinely shortest $a$ – $e$ walk is $a,e$ (length 1), which by the corollary is automatically a path (trivially, one edge, two distinct vertices).

This example illustrates a common subtlety: path-extraction from an arbitrary walk gives some path, not necessarily a minimum-length one, unless the input walk was already minimum-length.

Example 2 (A walk that is not a trail, and locating the cycle inside it). Let $H$ have vertices $\{1,2,3,4\}$ and edges $\{12, 23, 34, 41\}$ (a 4-cycle). Consider

T = 1, 2, 3, 4, 1, 2, 3.

Check adjacency: $12,23,34,41,12,23$ — all valid edges of $H$ . So $T$ is a walk of length $6$ from $1$ to $3$ .

Edges used, with multiplicity: $12$ appears at positions $1$ and $5$ ; $23$ appears at positions $2$ and $6$ . Two edges are each used twice. Hence $T$ is not a trail (edges repeat), and consequently not a path either (trails are necessary for paths, since path $\Rightarrow$ trail).
Vertices repeat too: vertex $1$ at positions $0,4$ ; vertex $2$ at positions $1, 5$ ; vertex $3$ at positions $2,6$ .
Extract a path from $1$ to $3$ via the proof's algorithm: find a repeated-vertex pair with minimal index gap. The repeated pairs are $(v_0,v_4)=(1,1)$ with gap $4$ , $(v_1,v_5)=(2,2)$ with gap $4$ , and $(v_2,v_6)=(3,3)$ with gap $4$ . All gaps are $4$ ; take the first found, $(v_0, v_4)$ . Excise the interior, giving $1, 2, 3$ (deleting the middle " $4$ " between the two $1$ 's and relabeling). Check: this is exactly the walk $1,2,3$ , using edges $12,23$ , with all vertices distinct — a valid path of length $2$ from $1$ to $3$ .
Independently, notice $T$ itself contains the cycle $1,2,3,4,1$ (its first four steps) as a genuine closed sub-walk with distinct interior vertices $1,2,3,4$ — a nice illustration that a "messy" walk can contain a clean cycle as a substructure even though the walk as a whole is not one.

Why each hypothesis is needed

u \neq v

Scope, edge cases & common traps

Situation	What holds	Common mistake
Walk between distinct $u,v$	Contains a path between $u,v$ (proved above)	Assuming the extracted path is automatically shortest
Closed walk ( $u=v$ )	May contain a cycle, or may not (e.g. trivial back-and-forth, or acyclic graph)	Assuming every closed walk of length $\ge 3$ yields a cycle
Multigraphs / parallel edges	Two parallel edges $e_1 \ne e_2$ between the same pair $u,v$ give a cycle of length $2$ : $u,e_1,v,e_2,u$	Forgetting that "cycle of length $\ge 3$ " is a simple-graph convention; multigraphs allow length-2 cycles
Loops	A loop at $v$ is sometimes counted as a cycle of length $1$ ; conventions vary by textbook	Silently assuming loops are automatically excluded
Trail vs. path	Every path is a trail, not conversely	Using "trail" and "path" interchangeably
Length convention	Length = number of edges, not number of vertices	Off-by-one errors counting vertices instead of edges

The mathematician behind it

Origins · 1 minLeonhard Euler and how this was discovered

Leonhard Euler

1707–1783 · 18th-century Basel and St. Petersburg/Berlin, founder of graph theory via the Königsberg bridges problem

Euler's 1736 resolution of the Seven Bridges of Königsberg problem is the founding act of graph theory, and it is precisely a theorem about the existence of a particular kind of closed trail — what we now call a circuit using every edge exactly once. To even state Euler's theorem one needs the trail/walk distinction made in this article: Euler's insight was that the question "can I walk the city crossing each bridge exactly once" is a question about trails (no edge repeated), completely independent of how many times any given intersection (vertex) is revisited. This separation of "no repeated edges" from "no repeated vertices" is the conceptual seed from which the modern definitions of walk, trail, path, and cycle all grew, later formalized rigorously in the 19th and 20th centuries as graph theory matured into an independent field.

History

- 1736 — Euler analyzes the Königsberg bridge problem, implicitly using the trail/edge-repetition distinction.

- 1852 — Francis Guthrie's four-color conjecture spurs systematic study of graph structure, including paths and cycles.

- 1857 — William Rowan Hamilton studies the "Icosian Game," motivating the modern notion of a Hamiltonian cycle (a path/cycle visiting every vertex).

- 1936 — Dénes Kőnig publishes the first systematic textbook on graph theory, formalizing walk/trail/path terminology.

- 1969 — Standard modern terminology (walk, trail, path, circuit, cycle) is consolidated in widely used textbooks, stabilizing the vocabulary used today.

Is a single vertex, with no edges traversed, considered a walk?

Yes. The definition allows length $k=0$ : the sequence consisting of just $v_0$ with no edges is the trivial walk. It is vacuously a trail (no edges to repeat) and vacuously a path (only one vertex, so no repetition is possible). This convention matters for base cases in inductive proofs and for stating that every vertex is trivially "connected to itself" by a path of length $0$ , which is needed to make the connectivity relation reflexive in Connectivity and Components.

Why do cycles require length at least 3 in a simple graph, but not necessarily in a multigraph?

In a simple graph there is at most one edge between any two vertices, so returning to your starting vertex after only $1$ or $2$ edges would either repeat the same edge (length 2: go out and immediately back along the only available edge) or not be a valid distinct-edge closed walk at all. A genuine cycle needs at least $3$ vertices to form a closed loop without reusing an edge. In a multigraph, however, two parallel edges between the same pair of vertices give a valid closed trail of length $2$ with no repeated edge, which is legitimately called a $2$ -cycle by some authors (conventions vary, so always check the source's definition).

Is every trail automatically a path, since repeated edges seem like they'd force repeated vertices anyway?

No — this is one of the most important distinctions in the article. A trail forbids repeated edges but permits repeated vertices, as long as those revisits use different edges. For instance, in a graph shaped like a "bowtie" (two triangles sharing a single vertex $v$ ), the trail that goes around one triangle back to $v$ and then around the other triangle revisits $v$ exactly once in the middle, using entirely different edges each time. This is a valid trail but not a path, because the vertex $v$ appears twice.

How does path extraction relate to finding shortest paths algorithmically?

The corollary that a minimum-length walk is automatically a path is exactly the theoretical justification for why breadth-first search, which explores walks in increasing order of length, correctly finds shortest paths without needing a separate check for repeated vertices. If BFS ever produced a shortest walk with a repeated vertex, that walk could be shortened by excision, contradicting minimality — so the algorithm's output is guaranteed path-like "for free," a fact that would otherwise require separate verification.

Does the path-extraction theorem hold in directed graphs as well?

Yes, with directed walks, trails, and paths defined analogously using directed edges (arcs) respecting orientation, the same excision argument applies verbatim: if a directed walk from $u$ to $v$ ( $u \ne v$ ) revisits a vertex, the sub-walk between the two visits can be excised, and the direction of all remaining edges is unaffected because we only delete a contiguous directed sub-walk and glue two already-compatible endpoints together. The proof techniques transfer without modification, though closed structures behave differently since "directed cycles" impose a consistent orientation constraint not present in the undirected case.

If a graph has no cycles at all (a tree or forest), what does that say about walks?

In an acyclic graph, between any two distinct vertices there is at most one path, and consequently every walk between two distinct vertices in a tree, however long and repetitive, extracts down to that unique path. This is because if two distinct paths existed between the same pair of vertices, their union would necessarily contain a cycle (a fact proved in Connectivity and Components), contradicting acyclicity. Trees are thus the extreme case where the "many possible walks, but a canonical extracted path" phenomenon of this article becomes as simple as possible: there is only one path to extract, no matter which walk you start with.