Hadwiger–Nelson problem

By the de Bruijn–Erdős theorem, a result of de Bruijn & Erdős (1951), the problem is equivalent (under the assumption of the axiom of choice) to that of finding the largest possible chromatic number of a finite unit distance graph.

According to Jensen & Toft (1995), the problem was first formulated by Nelson in 1950, and first published by Gardner (1960).

Hadwiger (1945) had earlier published a related result, showing that any cover of the plane by five congruent closed sets contains a unit distance in one of the sets, and he also mentioned the problem in a later paper (Hadwiger 1961).

One application of the problem connects it to the Beckman–Quarles theorem, according to which any mapping of the Euclidean plane (or any higher dimensional space) to itself that preserves unit distances must be an isometry, preserving all distances.

[3] The fact that the chromatic number of the plane must be at least four follows from the existence of a seven-vertex unit distance graph with chromatic number four, named the Moser spindle after its discovery in 1961 by the brothers William and Leo Moser.

This graph consists of two unit equilateral triangles joined at a common vertex, x.

[4] The lower bound was raised to five in 2018, when computer scientist and biogerontologist Aubrey de Grey found a 1581-vertex, non-4-colourable unit-distance graph.

[5] Mathematician Gil Kalai and computer scientist Scott Aaronson posted discussion of de Grey's finding, with Aaronson reporting independent verifications of de Grey's result using SAT solvers.

Kalai linked additional posts by Jordan Ellenberg and Noam Elkies, with Elkies and (separately) de Grey proposing a Polymath project to find non-4-colorable unit distance graphs with fewer vertices than the one in de Grey's construction.

[6] As of 2021, the smallest known unit distance graph with chromatic number 5 has 509 vertices.

The upper bound of seven on the chromatic number follows from the existence of a tessellation of the plane by regular hexagons, with diameter slightly less than one, that can be assigned seven colors in a repeating pattern to form a 7-coloring of the plane.