Hamiltonian cycle versus Eulerian path
An extension of the graph theory topic. An Eulerian path visits every edge once (like the Königsberg bridges), while a Hamiltonian cycle visits every vertex once — seemingly similar, but the second problem is far harder computationally (NP-hard, related to the traveling salesman problem). The concept was introduced by William Rowan Hamilton with his “Icosian game” in 1857.
I’ll give you a sequence of vertex degrees — decide the type of Eulerian route. Rule: 0 odd → cycle, 2 → path, otherwise → none.
What is a Hamiltonian cycle?
A Hamiltonian cycle is a route in a graph that visits every vertex exactly once and returns to the starting point. The name comes from the Irish mathematician William Rowan Hamilton, who in 1857 invented the “Icosian game” — a puzzle about finding such a route over the vertices of a dodecahedron, sold as the game “Around the World”.
Twins in looks, fundamentally different
At first glance a Hamiltonian cycle resembles an Eulerian path (from the Königsberg bridges problem), but the difference is fundamental: an Eulerian path is about edges (traversing all the roads), while a Hamiltonian cycle is about vertices (visiting all the cities).
This difference has huge computational consequences
For an Eulerian path there is a simple condition (the number of odd-degree vertices equals or ) and a fast algorithm. For a Hamiltonian cycle we know no fast (polynomial) algorithm — it is an NP-hard problem, computationally very hard, closely related to the traveling salesman problem and the famous question .
The two conditions are independent
A graph can have one, the other, both, or neither. The cube (8 vertices) has a Hamiltonian cycle but no Eulerian path — all its vertices have odd degree 3. The pentagon has both a Hamiltonian cycle and an Eulerian circuit. The envelope (the famous “draw without lifting your pen” puzzle) has an Eulerian path, and incidentally also a Hamiltonian cycle.
Why this matters for your exams:
Graph theory is not formally a separate exam topic, but this example teaches a valuable habit: a small change in the statement of a problem (edges → vertices) can turn an easy problem into a very hard one. Distinguishing “what exactly are we counting” — edges or vertices, elements or pairs — is the foundation of correct reasoning in combinatorics.
Remember: an Eulerian path = every edge once (easy, simple condition); a Hamiltonian cycle = every vertex once and a return (NP-hard). These are two different conditions — do not confuse them.
Theory & formulas
Two different conditions
- an Eulerian path/circuit — through every edge exactly once,
- a Hamiltonian cycle — through every vertex exactly once (returning to the start).
The difference in difficulty
For Euler there is a simple condition (the parity of vertex degrees). For Hamilton we know no fast criterion — it is an NP-hard problem, closely related to the traveling salesman problem.
Origin
The concept was introduced by Hamilton with his “Icosian game” (1857) — finding a cycle over the vertices of a dodecahedron.
Frequently asked questions
›What does a Hamiltonian cycle require?
Visiting every vertex of the graph exactly once and returning to the start.
›How does a Hamiltonian cycle differ from an Eulerian path?
An Eulerian path visits every edge once, while a Hamiltonian cycle visits every vertex once — two different conditions.
›Why is a Hamiltonian cycle harder?
We know no fast (polynomial) algorithm — it is an NP-hard problem, related to the traveling salesman problem.
Teaching? Embed this experiment on your site.
Free widget — paste it on your school site, blog or notes. It links to the full version.