Coloring the Plane

Imagine you have to paint every point of the infinite flat plane with colors obeying a single rule: two points that are exactly 1 unit apart must always get different colors. How many colors do you need?

This is the Hadwiger–Nelson problem, posed around 1950 by Edward Nelson (who was a student at the time) and popularized by Hugo Hadwiger. It sounds like a warm-up exercise. It is not. Seventy-five years later, mathematicians still do not know the answer.

What they do know is that the answer is 5, 6, or 7. The lower bound — you need at least 5 — was a shocking breakthrough made in 2018 by Aubrey de Grey, a biologist better known for research on aging. The upper bound — 7 colors always suffice — comes from a simple hexagonal tiling discovered in the 1950s. The gap between 5 and 7 has not budged since.

Paint the dots below by clicking them. Each click cycles through four colors. Try to color all 25 grid points so that no two dots exactly 1 unit apart share the same color, then press Check.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="canvas-wrap">
  <canvas id="plane" width="340" height="340" title="{{canvas_title}}"></canvas>
</div>
<div class="status" id="status">{{status_idle}}</div>
<div class="btns">
  <button id="btn-check" type="button">{{btn_check}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas-wrap { display: inline-block; border: 1px solid #cdd9e3; border-radius: 8px; overflow: hidden; }
canvas { display: block; cursor: pointer; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The grid spacing is 1 unit. This small integer grid can be 4-colored (a simple checkerboard-like pattern works). The Hadwiger–Nelson hardness comes from more complex finite point sets: de Grey found a unit-distance graph with 1581 vertices that provably requires 5 colors. This demo lets you feel the unit-distance constraint before confronting that deeper impossibility.

The problem lives at the intersection of graph theory, combinatorics, and measure theory. Here is what is known and why each piece is hard.

The upper bound: 7 colors always suffice. Tile the plane with regular hexagons of diameter slightly less than 1. Color the hexagons with 7 colors in a repeating pattern so that no two same-colored hexagons share a boundary or are within distance 1 of each other. Any two points in the same hexagon are less than 1 apart; any two points exactly 1 apart land in differently-colored hexagons. Done — 7 colors work.

The lower bound: 4 colors are not enough. For decades the best lower bound was 4, proved in the 1950s using the Moser spindle, a unit-distance graph on just 7 vertices that requires 4 colors. But 4 was stuck for nearly 70 years.

The 2018 breakthrough: 5 colors are not enough. In April 2018, Aubrey de Grey posted a paper on arXiv showing a unit-distance graph with 1581 vertices that cannot be properly colored with 4 colors — so the plane needs at least 5. The proof was computer-assisted: he generated and filtered candidate graphs until finding one where a SAT-like search confirmed no 4-coloring exists. Smaller examples (around 500–600 vertices) were quickly found by others, and a graph with just 510 vertices suffices today. This is the first improvement to the lower bound in 65 years.

Why 5, 6, or 7 seems so hard to close. No one has found a unit-distance graph requiring 5 colors (which would push the lower bound to 6), and no one has proved 5 colors are enough (which would close the problem). The difficulty is that unit-distance graphs are an extraordinarily rich family — there are infinitely many, with no simple structure to exploit. Measure-theoretic approaches (assigning colors randomly and using ergodic arguments) also hit walls. The problem connects to graph coloring in deep ways, but the infinite nature of the plane makes finite techniques hard to transfer.

The Hadwiger–Nelson problem is not just a curiosity — the question "can you assign labels to points so that nearby points never collide?" appears across applied mathematics:

• Frequency assignment in wireless networks: transmitters within a certain range of each other must use different frequencies. This is graph coloring on a geometric graph, and the chromatic number controls how many frequencies you need at minimum.
• Distance geometry: the problem is the simplest case of a broad class of questions about which distances can coexist in colored point sets. Results here feed into combinatorial geometry and the theory of Borel chromatic numbers.
• Combinatorics of the integers: the analogous problem on the integer line (color $\mathbb{Z}$ so that no two integers at distance $d$ share a color) is classical and fully solved — but the jump to $\mathbb{R}^2$ introduces enormous complexity.
• Computer-assisted proofs: de Grey's breakthrough was one of the most prominent uses of SAT solvers and automated combinatorial search in pure mathematics, inspiring a surge of interest in computer-assisted proof in combinatorics. See also graph coloring for the broader picture.

The problem is also a reminder that geometry can be deceptive: a question a child could state has defeated the best efforts of professional mathematicians for three quarters of a century.

The chromatic number of the plane is one of the most approachable open problems in mathematics: one sentence to state, one picture to illustrate, and yet completely unsolved after 75 years of effort by some of the sharpest minds in combinatorics.

The 2018 breakthrough by Aubrey de Grey showed that the answer is not 4 — a result that surprised everyone. But the gap between 5 and 7 remains. The next step — finding a unit-distance graph that needs 5 colors, or proving that 5 always suffice — could come from a human insight, from a more powerful SAT search, or from some angle nobody has tried yet.

Until then, the infinite plane keeps its secret: we know it needs at least 5 colors, we know 7 are always enough, and the truth lies somewhere in between. Sometimes the simplest questions are the last to fall — and this one may still have decades to go.