Math 2.0

Combinatorics Probabilistic and discrete-geometric methods Problem

Hadwiger–Nelson problem

Builds on GraphGraph colouringChromatic numberEuclidean distance

Problem

Let GG be the graph whose vertices are the points of the plane ℝ2\R^2. Two points pp and qq are adjacent exactly when their Euclidean distance is ∥p−q∥=1\norm{p - q} = 1. Determine the chromatic number χ(G)\chi(G) of this graph. Equivalently, colour every point of the plane so that any two points at distance 11 get different colours. Find the least number of colours that makes this possible. This number is called the chromatic number of the plane.

Remarks

The problem is open. The known bounds are 5≤χ(G)≤75 \le \chi(G) \le 7. The upper bound 77 comes from a tiling of the plane by regular hexagons of diameter slightly less than 11, coloured with 77 colours in a periodic pattern. The lower bound 44 follows from a finite unit-distance graph with 77 vertices, the Moser spindle, which has no proper colouring with 33 colours. In 2018 Aubrey de Grey found a finite unit-distance graph that needs 55 colours, which raised the lower bound to 55. By the de Bruijn–Erdős theorem (assuming the axiom of choice), χ(G)\chi(G) equals the largest chromatic number of a finite subgraph of GG.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph
Chromatic number, concept, no evidence levelChromatic numberconceptEuclidean distance, concept, no evidence levelEuclidean distanceconceptGraph, concept, no evidence levelGraphconceptGraph colouring, concept, no evidence levelGraph colouringconceptHadwiger–Nelson problem, problem, no evidence levelHadwiger–Nelson probl…problem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Chromatic number concept
  2. Euclidean distance concept
  3. Graph concept
  4. Graph colouring concept
  5. Hadwiger–Nelson problem problem

Further reading

  1. Web https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem
About this page
TagYX985SQG26
URIm2://YX985SQG26
Kindproblem
WritingW0 stub
MSC05C15, 52C10
StatusThis copy of the site has no build data. Run m2 status YX985SQG26.
AboutChromatic number
UsesGraph, Graph colouring, Chromatic number, Euclidean distance
Same as
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.