This is the four-color theorem, a famous result in topology. Now suppose we try to color the plane P so that no two points one unit apart ever have the same color. What is the minimum number of colors required? This is the chromatic number c (P) of the plane. The question was posed in 1950 by Edward Nelson, an American mathematician who was then a student, and published by Martin Gardner in his Scientific American column. It had already been studied by the Swiss mathematician Hugo Hadwiger, whose name, alongside Nelson's, is associated with the problem. They all recast the problem using graphs whose vertices represent regions of the plane and whose edges represent adjacency between those regions.
Four colors are necessary, as shown by the seven-vertex graphs of the brothers Leo and William Moser and the ten-vertex graph of Solomon Golomb.
The upper bound is due to the American mathematician John Isbell. He exhibited a seven-color solution: a tiling of the plane by regular hexagons with diameters slightly less than 1.
The latest advance comes from a British amateur mathematician. He has just published a paper establishing that c (P) ≥ 5. Aubrey de Grey, a biologist by profession and a mathematician in his spare time, sets out his arguments in about ten pages, combining unit-distance graphs with Moser spindles to produce a graph with 20,245 vertices (!), which he verified computationally could not be colored with four colors. Since then, Marijn Heule has helped simplify the graph, bringing it down to 826 vertices, but we still do not know whether c (P) = 5, 6 or 7.
