Chapter 1 · Graphs and Models
Walks, Trails, Paths, Cycles
Four words that decide whether your algorithm is linear or exponential — plus the cycle-removal lemma.
Informally we say "path" for everything. Formally the four notions differ, and the difference is exactly what makes Euler and Hamilton problems behave differently.
A walk of length k is a sequence v0, e1, v1, …, ek, vk of alternating vertices and edges. Then:
- trail = walk with all edges distinct,
- path = walk with all vertices distinct (⇒ all edges distinct, except in a multigraph where a path is by definition edge- and vertex-simple),
- cycle = closed trail (v0 = vk) with all other vertices distinct.
| object | repeat vertices? | repeat edges? | "find the longest …" |
|---|---|---|---|
| walk | yes | yes | matrix powers, O(n3 log k) |
| trail | yes | no | Euler tour, O(n+m) |
| path | no | no | Hamilton path, NP-complete |
| cycle | only the first = last | no | girth: O(nm); odd cycle: BFS |
If a walk from s to t exists, then a path from s to t exists, no longer than the walk.
Take a shortest walk W. If some vertex x occurs twice in W, W splits as s ⇝ x, a closed piece x ⇝ x, and x ⇝ t. Deleting the closed piece yields a strictly shorter walk from s to t, contradicting minimality. So no vertex repeats: W is a path. ∎
That 4-line proof is why BFS distance is well defined: shortest walk = shortest path, and we may search only over simple paths without ever saying so.
#The same lemma, weaponised
The proof above is the extremal principle (The Extremal Principle) in its purest form: choose a counterexample with the fewest edges and show the extra structure contradicts minimality. Most "prove there exists a path with property P" olympiad problems are this argument plus one case analysis.
- A connected graph contains a spanning tree: repeatedly delete an edge of a cycle; connectivity is preserved, and you stop when no cycle remains.
- A graph with n vertices and minimum degree δ ≥ 2 contains a cycle of length at least δ + 1 — take a longest path v0 … v_ℓ; all neighbours of v0 lie on it, and the farthest one closes a cycle that long.
#Directed version
Everything carries over with "walk" meaning a walk along the arrow direction, and one extra warning: in a digraph a path between u and v need not imply one between v and u. That asymmetry is what Orientations, In/Out-Degree, Strong vs Weak is about.
// Longest path in a DAG — the problem that is NP-hard on general graphs
// but trivial once there are no cycles to remove.
vector<int> order = topo_sort(); // see @directed/dag-toposort
vector<int> dp(n, -INF);
dp[s] = 0;
for (int u : order) if (dp[u] > -INF)
for (int v : g[u]) dp[v] = max(dp[v], dp[u] + w(u, v));"Longest path" on a general graph is NP-hard, so if a problem asks for it, look for the hidden constraint that makes cycles irrelevant: a DAG, a tree, small n, or weights that make revisiting never profitable (e.g. all-positive weights → longest finite walk is unbounded, so the answer must be about paths).