Euler's Eyes
2026-10-27
The Icosian game and Hamiltonian cycles
In 1856, still busy with non-commutative algebras, Hamilton invented the icosian calculus: three symbols $\iota$, $\kappa$ and $\lambda$ obeying the rules
$$\iota^2 = 1, \qquad \kappa^3 = 1, \qquad \lambda^5 = 1, \qquad \lambda = \iota\kappa.$$Today we would say they generate the group of rotations of the icosahedron, the solid with twenty triangular faces. Hamilton presented the calculus at a meeting of the British Association in Dublin in 1857, and noticed that it described paths along the edges of the dodecahedron, the solid with twelve pentagonal faces and twenty vertices.
The puzzle
To make the idea popular, Hamilton drew the dodecahedron flattened out on a board, with twenty holes at the vertices, each bearing the name of a city, and twenty numbered pegs. The challenge: start from a city, visit every other city exactly once, travelling only along the edges, and return to the starting point. In 1859 he sold the rights to the London games maker John Jaques and Son for 25 pounds. The game, sold as The Icosian Game and in a pocket version called The Traveller’s Dodecahedron, was a commercial failure: with a little patience the basic challenge is solved in minutes.
Try it. The letters are the consonants Hamilton used to name the cities:
Euler solves it, Hamilton does not
A route that passes once through every vertex and returns to its start is now called a Hamiltonian cycle. The question looks like a cousin of the bridges of Königsberg, where Euler wanted to cross every edge once. But the two are very different. For edges, Euler gave a simple criterion in 1736: just look at how many edges leave each vertex. For vertices, nobody knows a simple criterion. In 1972 Richard Karp included the Hamiltonian cycle problem in his list of NP-complete problems: whoever finds a fast method for it will have a fast method for thousands of other hard problems, and will win a million dollars from the Clay Institute.
Its most famous relative is the travelling salesman problem: among all the Hamiltonian cycles of a map, which is the shortest? It turns up in delivery routes, in drilling circuit boards and in DNA sequencing.
Exercise: counting the edges
In the dodecahedron, each of the 20 vertices touches 3 edges. How many edges are there? And how many of them does a Hamiltonian cycle use?
Counting by vertex there are $20 \times 3 = 60$ edge ends, and each edge has two ends: $60 / 2 = 30$ edges. A Hamiltonian cycle passes through 20 vertices and returns, using 20 edges; the other 10 are left out.
Exercise: a cycle on the cube
The vertices of the cube can be written as the sequences of three bits, from $000$ to $111$, joined when they differ in a single bit. Find a Hamiltonian cycle.
One solution: $000 \to 001 \to 011 \to 010 \to 110 \to 111 \to 101 \to 100 \to 000$. Each step changes a single bit. This sequence is the three-bit Gray code, used in position sensors and in error correction precisely because each step changes only one digit.
Sources: William Rowan Hamilton, “Memorandum respecting a new System of Roots of Unity”, Philosophical Magazine (1856) · Norman L. Biggs, E. Keith Lloyd and Robin J. Wilson, Graph Theory 1736–1936 (1976) · Richard M. Karp, “Reducibility among combinatorial problems” (1972) · the Icosian game at the Matemateca IME-USP.
All topics on William Rowan Hamilton · ← The Cayley–Hamilton theorem · The legacy of William Rowan Hamilton →