Graphs model routes, so we need words for routes. The words differ in what may repeat, and the differences matter in every later topic, from Euler circuits to shortest paths. Everything is built on the vertices and edges of graph basics.
Key idea
A walk is a sequence of vertices, each joined to the next by an edge; anything may repeat. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. A cycle is a closed trail (it ends where it starts) with no repeated vertex except that start and end. A graph is connected when every two vertices are joined by a path; its maximal connected pieces are its components.
Why it works
Why does it not matter whether "connected" is defined with walks or with paths? Any walk from $u$ to $v$ contains a path from $u$ to $v$: if some vertex repeats, cut out the detour between its two visits, and repeat until no vertex repeats. The result is shorter and still goes from $u$ to $v$. So "joined by a walk" and "joined by a path" mean the same thing, and the shortest route between two vertices is always a path.
| Name | repeated vertices? | repeated edges? | closed? |
|---|---|---|---|
| walk | allowed | allowed | either |
| trail | allowed | no | either |
| path | no | no | no |
| cycle | only start = end | no | yes |
Worked examples
Worked example: Naming routes
In the graph with edges $AB, BC, CA, CD, DE, EC$, classify $A \to B \to C \to D$, $A \to B \to C \to D \to E \to C$, $A \to B \to A \to C$ and $C \to D \to E \to C$.
- $A \to B \to C \to D$: no vertex repeats: a path.
- $A \to B \to C \to D \to E \to C$: $C$ repeats, but no edge does: a trail that is not a path.
- $A \to B \to A \to C$: the edge $AB$ is used twice: only a walk.
- $C \to D \to E \to C$: closed, no repeated edge, only the start repeated: a cycle.
Answer: path, trail, walk, cycle
Worked example: Counting components
A graph has vertices $A$ to $G$ and edges $AB$, $BC$, $DE$. How many components does it have?
- $\{A, B, C\}$ are joined. $\{D, E\}$ are joined. $F$ and $G$ have no edges.
- Each isolated vertex is a component by itself: $\{A, B, C\}$, $\{D, E\}$, $\{F\}$, $\{G\}$.
Answer: $4$
Common mistake
Mixing up walks, trails and paths. A route that passes through a crossroads twice is a trail, not a path, as long as it never reuses a road. And a walk that runs back and forth along one edge is not a trail. Check: first look for a repeated edge (then it is only a walk), then a repeated vertex (then it is a trail, not a path).
At least $n - 1$ edges are needed to connect $n$ vertices: each edge joins at most two components into one, and you start with $n$ separate vertices.