A walk may repeat vertices and edges. A trail cannot repeat edges, a path cannot repeat vertices, and a circuit or cycle is closed because it finishes at its starting vertex.
In an undirected graph, a sequence such as is valid only if each consecutive pair of vertices is joined by an edge. The distinctions depend on whether edges or vertices are repeated and whether the sequence is closed.
| Term | Precise meaning | Example |
|---|---|---|
| Walk | Vertices and edges may be repeated. |
| Trail | No edge is repeated, but vertices may be repeated. |
| Path | No vertex is repeated, so no edge is repeated. |
| Circuit | A closed trail: it starts and ends at the same vertex, with no repeated edges. Other vertices may repeat. |
| Cycle | A closed path: it starts and ends at the same vertex, with no other repeated vertices. |
These examples assume that every required edge exists. The restriction becomes progressively stronger: every path is a trail, and every trail is a walk. Every cycle is also a circuit, but a circuit is not necessarily a cycle because it may revisit a vertex.
A common misconception is that “circuit” and “cycle” are interchangeable. They are not: both are closed and avoid repeated edges, but only a cycle avoids repeated internal vertices.
This is AHL 3.16: Tree and cycle algorithms, so it is HL-only content and may appear in any GDC-active Math AI paper. In an exam, classify the route and justify it by checking three features in order: whether it is closed, whether any edge repeats, and whether any vertex other than the start/end repeats. This vocabulary supports Eulerian circuits, Hamiltonian cycles, and the Chinese postman problem.
