What are the different kinds of route through a graph, and when do special ones exist?
Distinguish walks, trails, paths, cycles and circuits, and determine when Eulerian and Hamiltonian routes exist.
How to tell walks, trails, paths, cycles and circuits apart, apply the odd-vertex condition for Eulerian trails and circuits, and recognise Hamiltonian paths and cycles.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
You must classify a given route, apply the odd-vertex test for Eulerian routes, and recognise Hamiltonian routes, which have no simple counting test.
The vocabulary of routes
The four route words form a hierarchy of restrictions.
The key distinction examiners test: a trail may revisit a vertex but never reuses an edge, whereas a path reuses neither.
Eulerian trails and circuits
An Eulerian trail uses every edge of a connected graph exactly once. Its existence depends only on how many vertices have odd degree.
This is a complete test: count odd-degree vertices and you know immediately whether an Eulerian route exists.
Hamiltonian paths and cycles
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle does so and returns to the start. Unlike the Eulerian case there is no simple degree test; you find a Hamiltonian route by trial, or argue none exists.
Edges versus vertices
The two ideas answer different questions. Eulerian routes are about using every edge once (the postman covering every street). Hamiltonian routes are about visiting every vertex once (the salesperson visiting every town). Keeping that contrast clear avoids most errors.