# Hadwiger–Nelson problem

The **Hadwiger–Nelson problem** asks for the chromatic number of the Euclidean plane: the minimum number of colors needed to color every point of the plane so that no two points at distance exactly 1 receive the same color.<sup>[1](https://mathworld.wolfram.com/Hadwiger-NelsonProblem.html)</sup> The answer, denoted \( \chi(\mathbb{R}^2) \), is known to be 5, 6, or 7, but the exact value has remained open since the problem was posed by [Edward Nelson](https://www.edgepedia.org/edward-nelson) in 1950.<sup>[1](https://mathworld.wolfram.com/Hadwiger-NelsonProblem.html)</sup><sup> • </sup><sup>[2](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)</sup>

| Key fact | Detail |
|---|---|
| Question | Minimum number of colors for the plane so that no two points at unit distance share a color; equivalently the chromatic number of the unit-distance graph on \( \mathbb{R}^2 \)<sup>[1](https://mathworld.wolfram.com/Hadwiger-NelsonProblem.html)</sup> |
| Origin | Posed by Edward Nelson in 1950, who showed at least 4 colors are needed; the upper bound of 7 is due to John Isbell (1950), using a hexagon tiling discussed by Hugo Hadwiger in 1945<sup>[3](https://artwaste.land/strata/coloring-the-plane/)</sup> |
| Current bounds | \( 5 \le \chi(\mathbb{R}^2) \le 7 \); the lower bound was raised from 4 to 5 by Aubrey de Grey in 2018<sup>[4](https://arxiv.org/abs/1804.02385)</sup> |
| de Grey graph | A 1,581-vertex unit-distance graph with no 4-coloring; the first version of the paper reported 1,567 vertices, corrected after Brendan McKay and Gordon Royle found that graph 4-colorable<sup>[4](https://arxiv.org/abs/1804.02385)</sup><sup> • </sup><sup>[3](https://artwaste.land/strata/coloring-the-plane/)</sup> |
| Smallest known witness | The 509-vertex, 2,442-edge graph of Jaan Parts (2020) is the smallest known 5-chromatic unit-distance graph in the plane<sup>[5](https://arxiv.org/abs/2010.12665)</sup><sup> • </sup><sup>[1](https://mathworld.wolfram.com/Hadwiger-NelsonProblem.html)</sup> |
| Reduction to finite graphs | By the de Bruijn–Erdős theorem, assuming the axiom of choice, the problem is equivalent to finding the largest chromatic number of a finite unit-distance graph<sup>[6](https://dmd2024.web.uah.es/files/Book_Proceedings_DMD%202024.pdf)</sup> |
| Measurable variant | If color classes must be measurable, at least 5 colors are necessary (Falconer, 1981)<sup>[7](https://link.springer.com/article/10.1007/s00454-016-9769-3)</sup> |

## Statement and reformulation

A coloring assigns one of finitely many colors to each point of \( \mathbb{R}^2 \), with the rule that any two points exactly one unit apart must differ. The least number of colors for which such a coloring exists is the chromatic number of the plane. In graph-theoretic terms, the problem asks for the chromatic number of the graph whose vertices are all points of the plane and whose edges join pairs at distance 1, the unit-distance graph; any finite set of points with its unit-distance edges is a unit-distance graph.<sup>[7](https://link.springer.com/article/10.1007/s00454-016-9769-3)</sup>

Lower bounds come from exhibiting finite unit-distance graphs that cannot be colored with few colors: if a finite graph needs \( k \) colors, the whole plane needs at least \( k \). Upper bounds come from explicit tilings of the entire plane.<sup>[2](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)</sup>

## Early bounds, 1950

Nelson observed that three colors are insufficient; an equilateral triangle of side 1 alone establishes that three colors are necessary.<sup>[2](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)</sup> Leo and William Moser later gave a compact seven-point configuration, the [Moser spindle](https://www.edgepedia.org/moser-spindle), proving that four colors are necessary.<sup>[2](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)</sup><sup> • </sup><sup>[8](https://elpais.com/ciencia/cafe-y-teoremas/2024-11-19/el-aprendizaje-automatico-ayuda-a-atacar-problemas-matematicos-clasicos.html)</sup>

For the upper bound, John Isbell showed in 1950 that seven colors suffice, using a tiling of the plane by regular hexagons of diameter slightly less than 1, colored in a repeating seven-color pattern so that same-colored hexagons are always separated by more than their diameter.<sup>[3](https://artwaste.land/strata/coloring-the-plane/)</sup><sup> • </sup><sup>[2](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)</sup> [Hugo Hadwiger](https://www.edgepedia.org/hugo-hadwiger) had discussed the same construction in 1945 in a different context, and Hadwiger himself disclaimed having posed the problem, though the name Hadwiger–Nelson stuck.<sup>[3](https://artwaste.land/strata/coloring-the-plane/)</sup>

For over 60 years nothing sharper was known in full generality: the bounds stood at \( 4 \le \chi(\mathbb{R}^2) \le 7 \).<sup>[7](https://link.springer.com/article/10.1007/s00454-016-9769-3)</sup>

## The 2018 breakthrough

In April 2018, Aubrey D. N. J. de Grey, a biogerontologist and computer scientist, published a family of finite unit-distance graphs that are not 4-colorable, raising the lower bound to 5.<sup>[4](https://arxiv.org/abs/1804.02385)</sup><sup> • </sup><sup>[9](https://www.sciencedirect.com/science/article/pii/S0012365X23001279)</sup> The smallest graph in his construction had 1,581 vertices after a correction: the first preprint reported 1,567 vertices, but Brendan McKay and Gordon Royle found that graph 4-colorable, and version 2 corrected the count to 1,581.<sup>[3](https://artwaste.land/strata/coloring-the-plane/)</sup> Verifying that four colors fail requires a computer search rather than visual inspection.<sup>[2](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)</sup>

The discovery triggered a collaborative Polymath project to verify the graph and find smaller examples.<sup>[2](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)</sup> Marijn J. H. Heule, using a method based on clausal proof minimization, computed several 553-vertex 5-chromatic unit-distance graphs in 2018, whose non-4-colorability can be mechanically validated in about a second.<sup>[10](https://arxiv.org/abs/1805.12181)</sup> A sequence of records followed: Heule graphs down to 517 vertices, and Parts graphs at 525, 510, and finally 509 vertices with 2,442 edges, obtained by a graph minimization method that preserves 5-chromaticity.<sup>[1](https://mathworld.wolfram.com/Hadwiger-NelsonProblem.html)</sup><sup> • </sup><sup>[5](https://arxiv.org/abs/2010.12665)</sup> As of August 2026, the 509-vertex Parts graph remains the smallest known 5-chromatic unit-distance graph realized in the plane, and no unit-distance graph in the plane with chromatic number greater than 5 is known.<sup>[1](https://mathworld.wolfram.com/Hadwiger-NelsonProblem.html)</sup>

A Lean 4 formalization verifies that the 510-vertex graph of Marijn Heule is not 4-colorable, giving a machine-checked proof that the plane needs at least 5 colors.<sup>[11](https://github.com/vasnesterov/HadwigerNelson)</sup>

## Six-colorings and machine learning

The upper bound of 7 comes from an explicit construction, so one route to progress is finding colorings with fewer colors or with relaxed constraints. A natural relaxation asks for six colorings in which five colors avoid unit distance and the sixth avoids a different distance \( d \). Such colorings were known only for \( \sqrt{2} - 1 \approx 0.414 \le d \le 1/\sqrt{5} \approx 0.447 \) for 30 years.<sup>[12](https://arxiv.org/abs/2404.05509)</sup>

In 2024, Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel, and Max Zimmer of the Zuse Institute Berlin and Technische Universität Berlin extended this range to \( 0.354 \le d \le 0.657 \) with two novel six-colorings, the first improvement in 30 years.<sup>[12](https://arxiv.org/abs/2404.05509)</sup> The constructions were derived by training a neural network to represent colorings of a specified type, an approach the authors called deep annealing, and then formalizing the colorings the network suggested; the resulting tilings are more irregular than previously known ones.<sup>[13](https://www.pokutta.com/blog/research/2024/07/28/hadwiger-nelson.html)</sup> A valid six-coloring with distances \( (1,1,1,1,1,1) \) would improve the upper bound to 6, and a five-coloring with \( (1,1,1,1,1) \) would solve the problem outright.<sup>[8](https://elpais.com/ciencia/cafe-y-teoremas/2024-11-19/el-aprendizaje-automatico-ayuda-a-atacar-problemas-matematicos-clasicos.html)</sup>

## Variants and related results

**Restricted colorings.** If color classes must be measurable sets, at least 5 colors are necessary, matching the unrestricted lower bound.<sup>[7](https://link.springer.com/article/10.1007/s00454-016-9769-3)</sup> If the plane is colored as a map, meaning regions bounded by Jordan curves, at least 6 colors are required; Woodall (1973) and Townsend (1981) established this, and Sokolov and Voronov showed in 2025 that at least 7 colors are required for maps whose boundaries are not arcs of a unit circle with three boundaries meeting at each vertex, and for colorings by arbitrary polygons.<sup>[7](https://link.springer.com/article/10.1007/s00454-016-9769-3)</sup><sup> • </sup><sup>[14](https://arxiv.org/abs/2502.01958)</sup>

**Multiple forbidden distances.** A direct generalization forbids two distances, 1 and \( d \), asking how many colors suffice so that no two points at distance 1 or \( d \) share a color; several values of \( d \) are known for which at least 5 colors are necessary.<sup>[15](https://arxiv.org/abs/1805.06055)</sup> For an interval of forbidden distances \( [1, b] \), the classic problem is the case \( b = 1 \), and improved bounds and exact values are known for some ranges of \( b \).<sup>[16](https://arxiv.org/abs/2201.04499)</sup>

**Axiomatic dependence.** The answer may depend on the foundations of set theory. Shelah and Soifer exhibited a distance graph on the real line whose chromatic number is 2 under the axiom of choice but uncountable in a model where every set of reals is Lebesgue measurable, showing that such chromatic numbers can be axiom-dependent; some mathematicians suspect the true answer to the Hadwiger–Nelson problem itself is unknowable in this sense.<sup>[3](https://artwaste.land/strata/coloring-the-plane/)</sup><sup> • </sup><sup>[2](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)</sup> The de Bruijn–Erdős theorem, which reduces the problem to finite graphs, uses the axiom of choice.<sup>[6](https://dmd2024.web.uah.es/files/Book_Proceedings_DMD%202024.pdf)</sup>

## Status

The chromatic number of the plane is 5, 6, or 7. Progress on the lower bound requires a finite unit-distance graph that is not 5-colorable; progress on the upper bound requires an explicit 6-coloring of the entire plane.<sup>[17](https://github.com/diangao/attackable-problems/blob/main/problems/001-hadwiger-nelson.md)</sup> No unit-distance graph in the plane with chromatic number greater than 5 is currently known.<sup>[1](https://mathworld.wolfram.com/Hadwiger-NelsonProblem.html)</sup>

## References

1. [Hadwiger-Nelson Problem, Wolfram MathWorld](https://mathworld.wolfram.com/Hadwiger-NelsonProblem.html)
2. [Patrick Honner, "Four Is Not Enough," Quanta Magazine (June 18, 2018)](https://www.quantamagazine.org/the-numbers-and-geometry-behind-a-math-coloring-puzzle-20180618/)
3. ["How Many Colors Does the Plane Need? Hadwiger–Nelson," artwaste.land](https://artwaste.land/strata/coloring-the-plane/)
4. [Aubrey D. N. J. de Grey, "The chromatic number of the plane is at least 5," arXiv:1804.02385 (2018)](https://arxiv.org/abs/1804.02385)
5. [Jaan Parts, "Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane," arXiv:2010.12665 (2020)](https://arxiv.org/abs/2010.12665)
6. [Proceedings DMD 2024](https://dmd2024.web.uah.es/files/Book_Proceedings_DMD%202024.pdf)
7. ["Fractional and j-Fold Coloring of the Plane," Discrete & Computational Geometry](https://link.springer.com/article/10.1007/s00454-016-9769-3)
8. [Juanjo Rué, "El aprendizaje automático ayuda a atacar problemas matemáticos clásicos," El País (2024)](https://elpais.com/ciencia/cafe-y-teoremas/2024-11-19/el-aprendizaje-automatico-ayuda-a-atacar-problemas-matematicos-clasicos.html)
9. ["Coloring distance graphs on the plane," Discrete Mathematics](https://www.sciencedirect.com/science/article/pii/S0012365X23001279)
10. [Marijn J. H. Heule, "Computing Small Unit-Distance Graphs with Chromatic Number 5," arXiv:1805.12181 (2018)](https://arxiv.org/abs/1805.12181)
11. [Hadwiger-Nelson Problem Formalization in Lean 4, GitHub](https://github.com/vasnesterov/HadwigerNelson)
12. [Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel, Max Zimmer, "Extending the Continuum of Six-Colorings," arXiv:2404.05509 (2024)](https://arxiv.org/abs/2404.05509)
13. [Sebastian Pokutta, "Extending the Continuum of Six-Colorings," research blog (2024)](https://www.pokutta.com/blog/research/2024/07/28/hadwiger-nelson.html)
14. [Georgy Sokolov, Vsevolod Voronov, "On the chromatic number of the plane for map-type colorings," arXiv:2502.01958 (2025)](https://arxiv.org/abs/2502.01958)
15. ["The Hadwiger-Nelson problem with two forbidden distances," arXiv:1805.06055 (2018)](https://arxiv.org/abs/1805.06055)
16. [Chybowska-Sokół, Junosza-Szaniawski, Węsek, "Coloring distance graphs on the plane," arXiv:2201.04499 (2022)](https://arxiv.org/abs/2201.04499)
17. [Attackable problems: Hadwiger-Nelson problem, GitHub](https://github.com/diangao/attackable-problems/blob/main/problems/001-hadwiger-nelson.md)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph invariants and parameters › Chromatic and coloring invariants*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026; Oct 25, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license