---
tag: YX985SQG26
kind: problem
name: Hadwiger–Nelson problem
msc: [05C15, 52C10]
uses: [00C0BR7D7H, 0NCPXH194Y, 0VHJRXNAAS, 0NPPGHQNXQ]
about: [0VHJRXNAAS]
sources:
  - url: https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem
same_as:
  wikidata: Q1383936
  wikipedia: Hadwiger–Nelson problem
history:
  posed_by: "Edward Nelson"
  first_stated: "1950"
---

## Problem

Let $G$ be the [[graph|00C0BR7D7H]] whose vertices are the points of the plane $\R^2$.
Two points $p$ and $q$ are adjacent exactly when their [[Euclidean distance|0NPPGHQNXQ]] is $\norm{p - q} = 1$.
Determine the [[chromatic number|0VHJRXNAAS]] $\chi(G)$ of this graph.
Equivalently, colour every point of the plane so that any two points at distance $1$ 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 \le \chi(G) \le 7$.
The upper bound $7$ comes from a tiling of the plane by regular hexagons of diameter slightly less than $1$, coloured with $7$ colours in a periodic pattern.
The lower bound $4$ follows from a finite unit-distance graph with $7$ vertices, the Moser spindle, which has no proper [[colouring|0NCPXH194Y]] with $3$ colours.
In 2018 Aubrey de Grey found a finite unit-distance graph that needs $5$ colours, which raised the lower bound to $5$.
By the de Bruijn–Erdős theorem (assuming the axiom of choice), $\chi(G)$ equals the largest chromatic number of a finite subgraph of $G$.

## Explanations

### L1 human

Paint every point of the plane with some colour.
The rule is that two points exactly one unit apart must get different colours.
What is the smallest number of colours that makes this possible?
Three colours are not enough, and seven colours are enough.
Today we know that at least five are needed, but whether the answer is $5$, $6$ or $7$ is unknown.