---
title: "Walks, Trails, Paths, Cycles"
summary: Four words that decide whether your algorithm is linear or exponential — plus the cycle-removal lemma.
difficulty: easy
tags: [definitions, proofs]
---

Informally we say "path" for everything. Formally the four notions differ, and the difference is exactly what makes Euler and Hamilton problems behave differently.

:::definition label="The hierarchy"
A **walk** of length $k$ is a sequence $v_0, e_1, v_1, \dots, e_k, v_k$ 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 ($v_0 = v_k$) with all other vertices distinct.
:::

| object | repeat vertices? | repeat edges? | "find the longest …" |
|---|---|---|---|
| walk | yes | yes | matrix powers, $O(n^3 \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 |

:::lemma title="Cycle removal"
If a walk from $s$ to $t$ exists, then a *path* from $s$ to $t$ exists, no longer than the walk.
:::

:::proof
Take a shortest walk $W$. If some vertex $x$ occurs twice in $W$, $W$ splits as $s \leadsto x$, a closed piece $x \leadsto x$, and $x \leadsto 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

:::idea title="Minimality arguments"
The proof above is the **extremal principle** (@proofs/extremal) 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.
:::

:::corollary label="Two useful consequences"
1. A connected graph contains a spanning tree: repeatedly delete an edge of a cycle; connectivity is preserved, and you stop when no cycle remains.
2. A graph with $n$ vertices and minimum degree $\delta \ge 2$ contains a cycle of length at least $\delta + 1$ — take a longest path $v_0 \dots v_\ell$; all neighbours of $v_0$ 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 @directed/definitions is about.

```cpp longest-path-dag.cpp
// 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));
```

:::trap title="\u03bc-shortcut"
"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).
:::

:::problems
- [[CF 1385E]] Directing Edges | https://codeforces.com/problemset/problem/1385/E | core | orientation, DAG
- [[CF 915D]] Almost Acyclic Graph | https://codeforces.com/problemset/problem/915/D | hard | is one vertex on every directed cycle? test all n candidates
:::