Skip to main content
Mind School·Wonder·Honor-system

The Hadwiger–Nelson Problem

How many colours does the plane need so no two same-colour points sit one unit apart?

Play It

▶

Coming Soon

Characterization

The Hadwiger–Nelson problem asks for the chromatic number of the plane: the minimum number of colours needed to colour every point in the Euclidean plane so that no two points exactly one unit apart share the same colour. Hugo Hadwiger posed a version of the problem in 1945; Edward Nelson formulated it independently in 1950 as a graduate student, and it was popularised by Martin Gardner. The answer has been bounded between 4 and 7 since the 1960s. The lower bound of 4 was established by the Moser brothers (Leo and William) in 1961, who constructed a small graph — the Moser spindle, seven vertices and eleven edges — that requires four colours. The upper bound of 7 comes from a simple hexagonal tiling argument. For over fifty years, these bounds did not budge. Then in April 2018, Aubrey de Grey — a biogerontologist, not a professional mathematician — constructed a graph of 1,581 vertices that cannot be coloured with four colours, raising the lower bound to 5. The result, published in Geombinatorics, was the first progress on the problem in decades and was subsequently refined by Marijn Heule and others using computational methods. The chromatic number of the plane is now known to be 5, 6, or 7. The Academy hosts the Hadwiger–Nelson problem in the Mind School because it is a colouring game on infinite paper — accessible to anyone with coloured pencils, open to everyone, and solved by no one.

Lineage

Hugo Hadwiger, "Überdeckung des euklidischen Raumes durch kongruente Mengen," Portugaliae Mathematica 4, 1945. Edward Nelson posed the problem in 1950; it was publicised by Martin Gardner in Scientific American (1960). Leo and William Moser, "Solution to Problem 10," Canadian Mathematical Bulletin 4, 1961. Aubrey de Grey, "The Chromatic Number of the Plane Is at Least 5," Geombinatorics 28(1), 2018. Marijn Heule, "Computing Small Unit-Distance Graphs with Chromatic Number 5," Geombinatorics 28(1), 2018. Alexander Soifer, The Mathematical Coloring Book (Springer, 2009), provides the definitive historical treatment.

Quests

Three quests — one for each archetype. Choose the one that fits your way of taking up the discipline.

  • Construct and colour a unit-distance graph of your own design — at least 15 vertices — and determine its chromatic number. Then attempt to extend the graph to force a higher chromatic number. Compare your construction to the Moser spindle (7 vertices, chromatic number 4) and, if possible, to de Grey's 5-chromatic graph. Record the graph (vertex coordinates and edges), the colouring, and what the construction process revealed about why raising the lower bound is difficult.

    No attestations yetOpen →
    Sign in to claim →

  • Draw the Moser spindle — the seven-vertex, eleven-edge unit-distance graph — with accurate unit distances. Attempt to colour it with three colours; observe the failure. Then colour it with four. Record the drawing, the failed three-colouring attempt (which edges forced the contradiction), and the successful four-colouring. Reflect on what the spindle reveals about the geometry of the plane.

    No attestations yetOpen →
    Sign in to claim →

  • Explain the Hadwiger-Nelson problem to a reader with no background in graph theory. Define the chromatic number of the plane; explain the Moser spindle and the hexagonal tiling argument that establish the bounds 4 ≤ χ ≤ 7. Cite Hadwiger (1945), Nelson (1950), and de Grey's 2018 result raising the lower bound to 5. Note that de Grey is an amateur mathematician and explain what his contribution illustrates about the accessibility of open problems in combinatorics.

    No attestations yetOpen →
    Sign in to claim →