Hamiltonian paths and cycles explained
Draw five dots in a ring, join each to its two neighbours, and you can walk round through every dot once and come home: a Hamiltonian cycle. Add a few edges or take some away and the question becomes surprisingly hard. Whether a graph has such a cycle is one of the best-known problems that no computer can yet answer quickly for every graph.
Every vertex once
A graph is a set of points, the vertices, joined by lines, the edges. A Hamiltonian path goes along edges and visits every vertex exactly once; a Hamiltonian cycle also returns to where it started, so it has as many edges as vertices. A graph with a Hamiltonian cycle is called Hamiltonian. Checking a proposed route is easy: count the vertices and look at each step. Finding one, or proving that there is none, is the hard part, because the number of orders in which the vertices could be visited grows like n!, already 2.4 × 10¹⁸ for 20 vertices.
Hamilton's Icosian game
William Rowan Hamilton, the Irish mathematician who discovered quaternions, invented the Icosian game in 1857. Its board showed a dodecahedron flattened into the plane, with its 20 corners marked by consonants, and the main task was to put pegs numbered 1 to 20 on the corners so that consecutive numbers, and 20 and 1, are joined by edges. Hamilton sold the rights for £25 to the London toy maker John Jaques and Son, who brought it out in 1859; it did not sell well. The puzzle has 30 solutions, counting a cycle once whatever its start and direction. The question itself was not new: Thomas Kirkman had asked which polyhedra have a cycle through all their corners in a paper sent to the Royal Society in 1855, and had shown one that has none.
Knight's tours
A knight's tour moves a chess knight so that it lands on every square exactly once: a Hamiltonian path in the graph whose vertices are the squares and whose edges are the knight's moves. A closed tour ends a knight's move from its start, a Hamiltonian cycle. Chess players set such puzzles more than a thousand years ago, and Euler studied them in a paper of 1759. In 1823 H. C. von Warnsdorff proposed always moving to the square with the fewest onward moves; this simple rule usually completes a tour of an 8 × 8 board without going back. A knight always changes square colour, so a closed tour needs as many light as dark squares, which rules out boards with an odd number of squares. Allen Schwenk showed in 1991 exactly which rectangular boards have a closed tour; among the squares, every one with an even side of 6 or more does. The standard chessboard has 13,267,364,410,532 closed tours, counted by Brendan McKay in 1997.
Graphs without a Hamiltonian cycle
The quickest proofs that there is no cycle are counting arguments. If the vertices can be coloured with two colours so that every edge joins different colours, a cycle alternates and needs as many vertices of each colour; a 5 × 5 grid has 13 of one and 12 of the other, so it has no Hamiltonian cycle. A cut vertex, whose removal splits the graph, would have to be passed twice, and a vertex of degree 1 cannot be passed at all. Some graphs escape all such arguments. The Petersen graph, published by Julius Petersen in 1898, has 10 vertices of degree 3 and no Hamiltonian cycle, yet deleting any one vertex leaves a graph that has one; it is the smallest such hypohamiltonian graph. The Herschel graph, named after Alexander Stewart Herschel, who wrote about the Icosian game in 1862, has 11 vertices and 18 edges and is the graph of a polyhedron with nine four-sided faces. No polyhedron with fewer corners lacks a Hamiltonian cycle. In 1884 Peter Guthrie Tait conjectured that every polyhedron with three edges at each corner has one; W. T. Tutte found a counterexample with 46 vertices in 1946.
Conditions that guarantee one
If a graph has many edges, a Hamiltonian cycle is certain. Gabriel Dirac proved in 1952 that a graph with n ≥ 3 vertices in which every vertex has degree at least n/2 has one, and Øystein Ore weakened the condition in 1960: it is enough that any two vertices that are not joined have degrees adding up to at least n. Both conditions only work in one direction. A plain ring of 100 vertices has degree 2 everywhere, far below 50, and is still a Hamiltonian cycle. That is the general picture: there are sufficient conditions and there are reasons for failure, and in between lies a large territory of graphs that only a search can decide.
Why no fast test is known
Deciding whether a graph has a Hamiltonian cycle is NP-complete; it was one of the 21 problems on Richard Karp's list of 1972. A method that solved it quickly for every graph would solve thousands of other problems quickly too, and would settle the P versus NP question. The contrast with Euler paths, which use every edge once, is striking: Euler showed in 1736 that counting the vertices of odd degree settles that question at once. The best exact methods for Hamiltonian cycles still take exponential time. Dynamic programming over all subsets of vertices, found by Richard Bellman and by Michael Held and Richard Karp in 1962, needs about n² × 2ⁿ steps, and Andreas Björklund's randomized method of 2010 about 1.657ⁿ. In practice backtracking with good pruning handles graphs of a few dozen vertices, and the traveling salesman problem, which looks for the shortest Hamiltonian cycle, is the weighted version of the same question.
Gray codes and the hypercube
Write the numbers 0 to 7 as 3-bit codes and join two codes when they differ in exactly one bit: the result is the graph of a cube. A Hamiltonian cycle through it, such as 000, 001, 011, 010, 110, 111, 101, 100, lists all eight codes so that each differs from the one before in a single bit. Such a list is a Gray code, named after Frank Gray of Bell Labs, who described it in a patent filed in 1947. Every hypercube has one: write the codes for one bit fewer, then the same list backwards, and put a 0 before the first half and a 1 before the second. Rotary encoders use Gray codes so that a reading taken between two positions is never more than one step wrong. The cube has 6 Hamiltonian cycles and the 4-bit hypercube 1,344.
Explore it
Open the Hamiltonian Path Explorer to try Hamilton's puzzle yourself, with dashed rings showing where you can go next, or switch to Search and watch backtracking work: the path grows, red dashes mark where it turns back, and the bars count the nodes at each path length. Switch the dead-end check, the connectivity check and Warnsdorff's order on and off, compare how many nodes each needs, count all the cycles of a small graph, or draw your own graph and see which of the quick tests apply.
Frequently asked questions
Is a graph with an Euler circuit also Hamiltonian, or the other way round?
Neither follows from the other. The bow tie, two triangles sharing a vertex, has an Euler circuit because every degree is even, but no Hamiltonian cycle, since the shared vertex would have to be passed twice. The complete graph K₄ has Hamiltonian cycles, but all four vertices have degree 3, so it has no Euler circuit.
Can a computer just try every order?
Only for small graphs. There are n! orders of n vertices, about 2.4 × 10¹⁸ for 20. Backtracking does much better, because it only follows edges and gives up on a partial path as soon as it is stuck: it finds all 30 cycles of the 20-vertex dodecahedron in about 1,400 steps. But for some graphs the number of partial paths still grows exponentially, and no method is known that avoids this for every graph.
Is the Hamiltonian path problem easier than the cycle problem?
No, both are NP-complete. Each can be turned into the other: add a new vertex joined to every old one, and the old graph has a Hamiltonian path exactly when the new one has a Hamiltonian cycle. In the other direction, a cycle problem becomes a path problem by adding a copy of one vertex, with the same neighbours, and a new end vertex attached to the vertex and another to its copy.
Why does a knight's tour on a 5 × 5 board have to start on a corner colour?
The 25 squares have 13 of the corner colour and 12 of the other, and a knight changes colour with every move. A tour of 25 squares alternates colours, so it starts and ends on the colour that has more squares. The app finds all 1,728 open tours of the 5 × 5 board, 864 if a tour and its reverse count once, and every one starts and ends on a corner-coloured square.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Open the Hamiltonian Path Explorer