How many colours the plane needs

The four-colour theorem is about maps: regions of the plane, and the rule that regions sharing a border get different colours. There is a question about colouring the plane that sounds almost the same and is completely different. Forget regions. Colour every single point of the plane, and require only that two points exactly one unit apart never share a colour. How many colours does that take?

Edward Nelson asked this in 1950, and the question has a peculiar history. Within weeks it was known that the answer is at least four and at most seven. Then for sixty-eight years nobody could improve either bound. In 2018 Aubrey de Grey, a biologist better known for work on ageing, found a set of 1,581 points in the plane that cannot be coloured with four colours, and the lower bound moved to five. The upper bound has not moved at all.

This essay draws the arguments for four and for seven exactly, and explains why the gap has been so hard to close.

From the plane to a finite graph #

A colouring of the whole plane is an infinite object, and there is no way to try them all. The problem becomes manageable by the observation that any lower bound can be proved with finitely many points.

Take some points in the plane, and join two of them whenever they are exactly one unit apart. This is a unit-distance graph. A colouring of the plane with no two points at distance one alike restricts to a proper colouring of the graph — if two joined points shared a colour, they would be two points at distance one sharing a colour. So if a unit-distance graph needs $k$ colours, the plane needs at least $k$.

The simplest example is an equilateral triangle of side one: three points, each pair one unit apart, needing three colours. So the plane needs at least three. To prove four, a graph needs more structure — some configuration of unit distances that three colours cannot accommodate. The search for that structure is exactly the problem of the previous essay turned inside out. There, a graph was given and the question was how few colours it needs; here the graph is chosen, from an infinite supply of points, to need as many colours as possible — and the only constraint on the choice is that every edge must be exactly one unit long. That constraint is what makes the problem hard. A graph needing five colours is easy to write down in the abstract; a graph needing five colours that can be drawn in the plane with every edge the same length is what took sixty-eight years.

The rhombus that fixes a colour #

The key configuration is a rhombus made of two equilateral triangles of side one sharing a side.

Suppose the plane is coloured with three colours and no two points at distance one match. In a rhombus, the two vertices of the shared side are one unit apart, so they have different colours — say red and blue. The centre is one unit from both, so it is neither: green. The far tip is also one unit from both, so it is green too. The two tips of a unit rhombus always share a colour. They are $\sqrt 3$ apart.

That single fact finishes the argument. The rhombus can be pivoted about the centre to any angle, so every point at distance $\sqrt 3$ from the centre shares the centre’s colour. The circle of radius $\sqrt 3$ is a single colour. But that circle is large enough to contain two points exactly one unit apart — the heavy chord in the figure — and those two must differ. Contradiction: three colours are not enough.

The argument uses infinitely many rhombi, one for each point of the circle. It needs only two.

Seven points: the Moser spindle #

Take two rhombi sharing the centre point, and pivot one relative to the other until their far tips are exactly one unit apart. That is seven points — the shared centre, two side pairs, two tips — and eleven unit edges, including the one between the tips. It is the Moser spindle, found by the brothers Leo and William Moser in 1961.

The rhombus argument applies to each rhombus separately: with three colours, each tip takes the centre’s colour. So the two tips share a colour — and they are joined by an edge. No three-colouring exists. The opening figure checks this the blunt way, by trying all $3^7 = 2{,}187$ colourings and finding none that works, and finds that four colours succeed in 384 ways. The spindle is a finite certificate that the plane needs at least four colours.

The picture is worth reading closely, because every edge in it is exactly one unit and nothing else in it is. The two rhombi are tilted by an angle whose sine is $1/(2\sqrt 3)$ on either side of the horizontal — precisely the tilt that puts the tips one unit apart — and at any other tilt the edge between the tips would not be there and the graph would be three-colourable. The spindle is rigid in exactly the way the argument needs.

A second route to four #

The spindle is not the only small graph that needs four colours. Solomon Golomb found another, with ten points and eighteen unit edges.

The argument is different in flavour. The centre and the hexagon form six equilateral triangles, so in any three-colouring the hexagon’s vertices alternate between the two colours the centre does not have. That puts vertices 1, 3 and 5 — alternate vertices of the hexagon — all in one colour. But the small triangle’s corners are each joined to one of those three vertices and to each other, so the small triangle has three corners that must avoid a single colour and also differ from each other: three colours for a triangle, with one colour forbidden. Impossible. The exhaustive search agrees. The two graphs reach the same conclusion by different routes, and the difference matters to anyone trying to go further. The spindle forces two distant points to share a colour and then joins them; the Golomb graph forces a whole set of points to share a colour and then attaches a triangle that cannot avoid it. De Grey’s construction, fifty years later, combined both habits on a much larger scale: pieces that force colours to repeat in controlled patterns, glued so that the patterns collide.

For decades these two graphs, and larger relatives built from them, were the whole story on the lower side. Every attempt to find a unit-distance graph that needed five colours failed, and a good many people suspected the answer was four.

Seven colours from hexagons #

The upper bound came from John Isbell almost as soon as the question was asked, and it is a single picture.

Tile the plane with regular hexagons, and colour them in a repeating pattern of seven, in which each hexagon’s six neighbours all have different colours and differ from its own. Then make two checks. Within a hexagon, no two points are one unit apart, provided the hexagon’s diameter — twice its side — is less than one. Between two hexagons of the same colour, the nearest points are further apart than one, provided the hexagons are far enough apart. In the seven-colour pattern, same-coloured hexagons have centres $\sqrt{21}$ side-lengths apart, so the nearest points are $\sqrt{21}\,s - 2s$ apart for side $s$.

Both conditions hold together only in a narrow range of sizes.

The window is from $1/(\sqrt{21} - 2) \approx 0.387$ to $0.5$. Any side in that range gives a valid seven-colouring of the plane — with a convention for which hexagon owns the points on each boundary, since a boundary point belongs to two hexagons and has to be given one colour.

Why seven, and not six? A six-colouring by a similar tiling would need same-coloured tiles further apart relative to their size than any tiling pattern with six colours allows; nobody has found one, of any shape, and it is widely suspected there is none. But suspicion is not proof, and six is not ruled out.

The same seven on a doughnut #

The seven-colour hexagon pattern has appeared before, in a different guise, and the coincidence is not an accident.

Seven regions on a doughnut showed that a map on the surface of a torus can need seven colours: there is a map of seven regions on a torus in which every region touches every other. Take the hexagonal colouring above and look at a single block of seven hexagons, one of each colour. The pattern repeats by two translations, and gluing opposite sides of a suitable parallelogram of the tiling together — wrapping the plane onto a torus so that the repeat becomes the identity — leaves exactly seven hexagons, each touching the six others. That is the seven-region torus map. The plane’s seven-colouring is the torus map unrolled and repeated.

So the same pattern answers two different questions: on the torus it is the worst case, forcing seven colours for maps; in the plane it is the best known case, achieving seven colours for points. The torus theorem is exact because Heawood’s counting bound meets the example. The plane question is open because nothing like that counting bound exists for unit distances — there is no Euler’s formula that limits how many unit-distance constraints a set of points can carry, and the rhombus argument is the closest thing the subject has to one.

Five, in 2018 #

De Grey’s graph was built in stages from spindle-like pieces. The central idea was a configuration that forces a particular pattern of colours — rather than merely forcing two points to share a colour, as the rhombus does — and then showing that copies of it, rotated and overlapped, force a contradiction when only four colours are available. The final graph had 1,581 vertices, and its four-colour impossibility was checked by computer, since no human argument covers every case.

The result was taken up at once by a collaborative online project, Polymath16, which simplified the construction, found smaller examples and checked them independently with several different satisfiability solvers. The smallest known unit-distance graph needing five colours now has a few hundred vertices, and it too is certified by computer rather than by an argument a person can read in full. The situation resembles the four-colour theorem: a finite fact, completely checked, with no short explanation.

So the chromatic number of the plane is 5, 6 or 7. Most people who have worked on it now expect the truth to be larger than five, though for no better reason than that the lower bound has just moved and the upper bound has seemed too natural to be beaten.

Why a finite graph is always enough #

There is a theorem that explains why the search for the answer has always been a search for finite graphs, and it is less innocent than it looks.

Nicolaas de Bruijn and Paul Erdős proved in 1951 that if every finite subgraph of an infinite graph can be coloured with $k$ colours, so can the whole graph. So if the plane truly needs five colours, some finite set of points already needs five — as de Grey’s does — and if it needs seven, some finite unit-distance graph needs seven. The question about the infinite plane is equivalent to a question about all finite configurations in it.

The proof for countable graphs is König’s lemma: an infinite, finitely branching tree of partial colourings, one level for each vertex added, has an infinite branch, and that branch is a colouring of everything. The plane is uncountable, and for uncountably many points the same step needs the axiom of choice or a close relative. Without it, the equivalence can fail. Saharon Shelah and Alexander Soifer showed in 2003 that there are axiom systems, weaker than the usual ones, in which the answer to the question for the whole plane could differ from the answer for its finite subgraphs.

And if the colour classes are required to be reasonable sets — measurable, so that they have areas — the answer is known to be at least five, by Kenneth Falconer in 1981, decades before de Grey’s graph. The measurable version and the unrestricted version need not have the same answer, and nobody knows whether they do.

Counting the colourings that do work #

The searches behind the figures report more than a yes or no. The spindle has 384 proper colourings with four colours and none with three; the Golomb graph has 2,280 with four. Those numbers are values of each graph’s chromatic polynomial — the polynomial that counts proper colourings with $k$ colours — at $k = 4$, and the zero at $k = 3$ is a root. A graph needs four colours exactly when three is a root of its chromatic polynomial and four is not.

For the unit-distance graphs that matter, the polynomial is not a practical tool: de Grey’s graph has 1,581 vertices and its polynomial is out of reach. But the counts carry a small piece of information the yes-or-no does not. Every four-colouring of the spindle is forced to give its two tips different colours — the edge between them sees to that — and the 384 colourings are the ways of doing so; a graph needing five colours has, by contrast, exactly zero four-colourings, and the computer searches that certify de Grey’s example are searches for a single one and a proof that there is none. It is the same kind of certificate the four-colour proof relies on, turned the other way.

What the pictures cannot show #

Each figure is exact. The spindle and the Golomb graph have been checked edge by edge to be unit-distance graphs and colouring by colouring to need four colours; the hexagons have been checked to satisfy both conditions. What none of them can show is the gap between five and seven, because showing it would need either a colouring of the plane with fewer than seven colours or a finite graph needing more than five, and neither is known.

The figures are also silent about boundaries. The hexagonal colouring assigns every point a colour, but the drawing shows filled hexagons; the points on the edges between them have to be distributed by a rule, and a careless rule puts two points one unit apart — one on each end of a long diagonal of the tiling — into the same colour. The standard convention gives each hexagon the part of its boundary on one side, and the argument goes through, but the picture cannot display it.

And the pictures give no hint of how hard it is to find a graph like de Grey’s. The spindle is found by reasoning; graphs needing five colours were found only after a new idea and a large computation. Small configurations, as far as anyone has searched them, can all be four-coloured, which is what kept the lower bound at four for so long.

Still open: five, six or seven #

The question Nelson asked in 1950 is open in the precise sense that its answer is one of three numbers and nobody knows which. The upper bound of seven has not been improved since it was found; the lower bound of five is six years old and certified by computer. Whether there is a unit-distance graph needing six colours, and whether there is any colouring of the plane with six, are both unknown.

The neighbouring questions are open too. For three-dimensional space the chromatic number is known only to lie between 6 and 15. For the plane with only rational coordinates, the answer is 2 — the points at rational distance one from each other form a graph with no odd cycles — so the difficulty is entirely in the irrational distances that the rhombus and the spindle exploit. And the question whether the answer depends on the axioms of set theory — whether the plane’s chromatic number is even a well-defined number independent of how the colour classes are allowed to look — has been sharpened but not settled. For the everyday axioms, with choice, the de Bruijn–Erdős theorem makes the question entirely finite: the answer is the largest chromatic number of any finite unit-distance graph. That turns an infinite problem into an infinite search over finite objects — which is exactly the kind of search that computers have now contributed to twice, and which gives no guarantee of ever ending.