The Hadwiger–Nelson Problem

Imagine you must paint every single point of an infinite sheet of paper, with one rule: any two points that are exactly distance 1 apart must get different colors. What is the smallest number of colors that lets you do it?

That one sentence is the Hadwiger–Nelson problem, posed around 1950. The number it asks for is called the chromatic number of the plane. You might guess it's some clean value — but here is the surprise: after more than seventy years, nobody knows.

We have only managed to trap it between two walls. The answer is at least 5 and at most 7 — and which of the values 5, 6, or 7 is correct remains open to this day. This article shows where those walls come from, and lets you feel the lower one with your own hands.

You can't experiment on an infinite plane, but you can on a tiny piece of it. Below is the Moser spindle: seven points where every drawn line connects two points that are exactly distance 1 apart. If even this little gadget can't be colored with few colors, then neither can the whole plane.

<p class="hint">{{hint}}</p>
<div class="palette" id="palette"></div>
<svg id="graph" viewBox="0 0 276 249" role="img" aria-label="{{graph_aria}}"></svg>
<div class="status" id="status">{{status_default}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="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; }
.palette { display: flex; gap: .5rem; margin: .2rem 0 .4rem; flex-wrap: wrap; }
.swatch { width: 30px; height: 30px; border-radius: 50%; cursor: pointer;
          border: 3px solid #fff; box-shadow: 0 0 0 1px #bbb; }
.swatch.sel { box-shadow: 0 0 0 3px #1d3557; }
svg { width: 100%; max-width: 320px; height: auto; display: block; margin: .2rem 0; }
.edge { stroke: #9aa6b2; stroke-width: 2; }
.edge.bad { stroke: #e63946; stroke-width: 3.5; }
.node { stroke: #1d3557; stroke-width: 2; cursor: pointer; }
.node:hover { stroke-width: 3.5; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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

Pick a color and click the points, trying to use only 3 colors with no two connected points matching. It is impossible — the spindle is built so that three colors always force a clash, which is exactly why the plane needs at least 4 (and, as we'll see, at least 5). Press Show it needs 4 to watch the proof play out.

What makes this problem so stubborn? The two walls are built in completely different ways.

• Upper bound — 7 colors are enough. Tile the plane with hexagons slightly smaller than diameter 1 and color them in a repeating pattern of 7 colors. No two same-colored points ever land exactly 1 apart. So you never need more than 7.
• Lower bound — at least 4, the easy way. The Moser spindle (1961) is a 7-point unit-distance graph that cannot be 3-colored. Since these seven points live in the plane, the plane itself needs at least 4 colors. You just proved this in the demo above.
• Lower bound — at least 5 (the breakthrough). In 2018, Aubrey de Grey built a unit-distance graph with 1581 vertices that cannot be 4-colored, pushing the lower bound from 4 up to 5. It was the first improvement in over 60 years and was confirmed by computer (a SAT solver).
• Still open. That leaves the answer pinned between 5 and 7. Whether it is 5, 6, or 7 is an unsolved problem — no Millennium Prize, no author, no year, just an honest gap.

Notice the flavor: the lower bound is a giant graph coloring problem, and verifying de Grey's graph is "really uncolorable" was itself a massive SAT computation. The hardness here isn't a single algorithm running slowly — it's that we don't even know which answer to aim for.

"Assign labels so that things too close together never collide" is a pattern that shows up far beyond geometry:

• Frequency assignment: transmitters within range of each other must use different channels — a coloring problem on a graph of "who interferes with whom."
• Combinatorial geometry: unit-distance graphs feed dozens of distance-based questions, like how many times one distance can repeat among n points.
• SAT and computer-assisted proofs: de Grey's lower bound was nailed down by a SAT solver, and the search for smaller hard graphs is still a live computational sport.
• Coloring theory: the problem is a clean, famous testbed for graph coloring ideas, where small gadgets force global constraints.

The Hadwiger–Nelson problem is what mathematicians call "elementary but not easy": a child can understand the question, yet it sits at the frontier of what we can prove.

The Hadwiger–Nelson problem is a perfect little monument to how thin the line is between simple to ask and impossible to answer. Seven hexagons show you never need more than 7 colors; a 7-point spindle shows you need at least 4; and de Grey's sprawling 1581-point graph drags the floor up to 5. Between 5 and 7 lies a question that has outlasted generations of mathematicians.

So when the demo above refuses your third color, you're not failing — you're touching one wall of a genuinely open problem. Like P vs NP, it's a reminder that some of the most natural questions we can imagine still have no answer at all.