Complete graph
Named by 13 essays across 3 fields — each of them below, with the objects they name alongside it.
Six people at a party
Among any six people, three are mutual acquaintances or three are mutual strangers. Five is not enough, and the arrangement that saves five is a pentagon. Beyond that the numbers become unknowable.
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.
Two graphs that will not lie flat
Five points, every pair joined: no matter how the points are placed or how the lines are drawn, two of the lines cross. The proof is not about drawing at all — it counts edges against faces and finds one edge too many.
Seven regions on a doughnut
A map on a torus can need seven colours, and the proof is a picture — seven regions, each sharing a border with all six others. The plane needed a computer and eighty-six years; the harder surface was settled in 1890 by drawing something.
Eighteen people, and the seventeen that escape
Among any eighteen people, four are mutual acquaintances or four are mutual strangers. Seventeen can be arranged so that neither happens, and the arrangement is not a lucky find — it is a rule about squares.
The colouring nobody has ever seen
Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.
Five spokes squeezed into K5
The Petersen graph has no point with four neighbours, so no stretched copy of K5 can sit inside it. Contract its five spokes and K5 appears anyway. Kuratowski's theorem forbids stretched copies and Wagner's forbids squeezed ones, the two notions disagree on this graph — and they still name exactly the same planar graphs.
Six points in space and a pair that must link
Put six points anywhere in space and join every pair with a straight segment. Split the six into two triangles — there are ten ways — and at least one of the ten pairs of triangles is linked like two rings of a chain. No placement avoids it. The reason is a parity: moving an edge through another changes exactly two of the ten linking numbers, so their sum stays odd whatever is done.
The fewest corners a surface needs
Build a closed surface from triangles, any two meeting along a whole edge, at a single corner or not at all, and ask for the fewest corners. Two lines of counting give a floor for every surface, in terms of its Euler characteristic alone. The torus meets it with seven, the projective plane with six — and the Klein bottle, which the counting says could be built from seven, cannot, as a search of every possible arrangement shows.
The crossings a graph cannot avoid
Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.
A labelling every tree seems to have
Number the points of a tree 0 to n − 1 and write on each edge the difference of the numbers at its ends. The labelling is graceful if the edges then carry 1 to n − 1, each exactly once. Every tree anyone has ever checked — every one of the 551 trees on twelve points, and every tree up to about thirty-five — has such a labelling, and no one knows why. A graceful tree also tiles a complete graph by rotation, which is why the question was asked.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Counting argumentExhaustive searchGraphGraph colouringParityPlanarityEuler formulaExistence proofPlanar graphProbabilistic methodRamsey numberConjecture