Hamiltonian cycles — the series
-
A walk that changes one thing at a time
Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.
-
Every place changes back
A closed walk through every corner of a cube changes one place at each step, and each place, having changed, must change back before the walk returns home. So every place changes an even number of times — which is why no walk on three places can share the work evenly, why perfect sharing is possible only when the number of places is a power of two, and what sorts the 1,344 walks on the 4-cube into exactly four kinds.
-
The walk through the middle levels
On seven places, the words with three ones and the words with four number thirty-five each. Is there a closed walk through all seventy, changing one place at a time and never leaving those two levels? On five places the answer is 24 walks, on seven and nine a search finds one in moments — and whether one exists for every odd length was open for thirty years, until Torsten Mütze proved in 2016 that it always does.
-
The symmetric graphs no tour can close
Take the words of five places with two ones and join two when they share no one. The ten words look exactly alike to the graph, and no closed tour runs through them — because every way of leaving out one edge at each word leaves two pentagons. Only four connected graphs this symmetric are known to fail like that, and nobody knows whether a fifth exists.
-
Half the neighbours forces a tour
Deciding whether a graph has a closed tour through every point is one of the hardest problems computers are asked to solve. Gabriel Dirac found a condition that settles it in one glance: if every point is joined to at least half the others, a tour exists. The proof is a counting argument on a single path, it runs as an algorithm, and two small graphs show that the half cannot be lowered — while random graphs show how much stronger than necessary it is.
-
The boards a knight can tour
A knight can visit every square of a chessboard once and land a move from where it began. On a 5 × 5 board it cannot, on a 4 × 100 board it cannot, and on a 3 × 8 board it cannot, though on 3 × 10 it can in sixteen ways. Allen Schwenk found in 1991 the complete list of rectangles without a closed tour, and the reasons on it are of two kinds — a colouring that counts squares, and a second colouring that a tour would have to make agree with the first.
-
The tour arrives with the last second neighbour
Add the edges between n points one at a time in a random order. A tour through every point cannot exist while some point has fewer than two neighbours, and in a large random graph that is the only thing stopping it: the tour appears at the very edge that gives the last point its second neighbour. Watched in thousands of small graphs, the coincidence is already the rule, and the exceptions are tiny traps around the points of lowest degree.
-
One tour through every position of the Tower of Hanoi
Draw every position of the Tower of Hanoi as a point and every legal move as a line, and the picture is a Sierpiński triangle. The famous shortest solution runs straight down one side of it, spelling the binary Gray code as it goes. The slowest honest solution threads through every position once and spells the ternary one. And unlike the cube the binary Gray code walks, which has 1,344 closed tours at four dimensions, the triangle has exactly one at every size.