Concept

Hamiltonian cycle

A closed path in a graph that visits every point exactly once. Deciding whether one exists is hard in general; complete graphs have many, and they are the cycles that seating plans, travelling salesman tours and knotted paths through points are made of.

Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.

A single table for 9 guests over 4 nights. Small circles of 9 guests, one per night, each showing the night's seating as a closed zigzag path; every pair of guests is adjacent in exactly one of them.

Every pair side by side, once

Seat an odd number of guests at round tables for as many nights as it takes, the same table sizes every night, so that every two guests sit side by side on exactly one night. For a single table a zigzag turned a notch each night does it for any number of guests. For other table plans the answer is almost always yes — and for six guests at two tables of three, nine at tables of four and five, and eleven at three, three and five, an exhaustive search proves it is no.

probability · Inclusion exclusion

Seven points in space and a knotted path through all of them, seed 12. A projection of K₇ with straight edges, faint, and one Hamiltonian cycle drawn heavy with its crossings broken: a trefoil. 9 of the 360 Hamiltonian cycles are knotted.

Seven points and a knot they cannot avoid

Put seven points anywhere in space and join every pair with a straight segment. There are 360 closed paths that visit all seven points once each, and at least one of them is knotted — however the points are placed. The reason is a parity, as it was for six points and a linked pair: a number read off each path's knot adds up, over all 360, to something odd. Six points are not enough; seven always are.

topology · Linking number

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.

discrete · Hamiltonian cycles

Closing a path into a tour: the crossing pair the counting forces. A path through 10 points in a row, arcs from its two ends to their neighbours, and the crossing pair at step 3 whose two arcs replace that step to make a closed tour.

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.

discrete · Hamiltonian cycles

A closed knight's tour of the 8 × 8 board. A 8 by 8 chequered board with a closed polygon joining the centres of all 64 squares in the order a knight visits them.

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.

discrete · Hamiltonian cycles

Named alongside it

The objects these essays reach for when they reach for this one.

Bipartite graph Exhaustive search Complete graph Parity Alexander polynomial Complexity Counterexample Degree Fano plane Graph decomposition Greedy algorithm Heuristic

All concepts