Introduction

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.

Color the Spindle

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">This is the <b>Moser spindle</b> — 7 points whose every drawn edge is <b>exactly distance 1</b> apart. Pick a color, then click points so that no two connected points share a color. Try to finish with only <b>3 colors</b>: you can't — some edge is always forced to clash.</p>
<div class="palette" id="palette"></div>
<svg id="graph" viewBox="0 0 276 249" role="img" aria-label="Moser spindle graph"></svg>
<div class="status" id="status">Color all 7 points. Avoid same-color neighbors.</div>
<div class="btns">
  <button id="check" type="button">Check coloring</button>
  <button id="auto" type="button">Show it needs 4</button>
  <button id="reset" type="button" class="ghost">Clear</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Hadwiger–Nelson: how many colors to paint the plane so no two points exactly distance 1 apart share a color? A "unit-distance graph" is any finite set of points whose edges are pairs at distance exactly 1; its chromatic number is a lower bound for the plane. The Moser spindle (7 points, 11 unit edges) is NOT 3-colorable, which is why the answer is at least 4. (de Grey, 2018, pushed the lower bound to 5 with a far larger unit-distance graph.) Here we demo the spindle.
const POS = { A:[30,125], B:[119,30], C:[157,154], F:[246,60], D:[157,95], E:[119,219], G:[246,190] };
const EDGES = [['A','B'],['A','C'],['A','D'],['A','E'],['B','C'],['B','F'],['C','F'],['F','G'],['D','E'],['D','G'],['E','G']];
const NAMES = Object.keys(POS);
const COLORS = ['#e63946', '#2a9d8f', '#e9c46a', '#577590']; // red, teal, gold, slate
const NAMECOL = ['Red', 'Teal', 'Gold', 'Slate'];

let palette = [0, 1, 2]; // start with only 3 colors offered
let sel = 0;             // selected color index
const color = {};        // node -> color index (or undefined)

function buildPalette() {
  const p = document.getElementById('palette'); p.innerHTML = '';
  palette.forEach(ci => {
    const s = document.createElement('div');
    s.className = 'swatch' + (ci === sel ? ' sel' : '');
    s.style.background = COLORS[ci];
    s.title = NAMECOL[ci];
    s.addEventListener('click', () => { sel = ci; buildPalette(); });
    p.appendChild(s);
  });
}

function badEdges() {
  return EDGES.filter(([a, b]) =>
    color[a] !== undefined && color[b] !== undefined && color[a] === color[b]);
}

function render() {
  const svg = document.getElementById('graph');
  const bad = new Set(badEdges().map(e => e.join('-')));
  let s = '';
  EDGES.forEach(([a, b]) => {
    const cls = bad.has(a + '-' + b) ? 'edge bad' : 'edge';
    s += `<line class="${cls}" x1="${POS[a][0]}" y1="${POS[a][1]}" x2="${POS[b][0]}" y2="${POS[b][1]}"/>`;
  });
  NAMES.forEach(n => {
    const fill = color[n] === undefined ? '#ffffff' : COLORS[color[n]];
    s += `<circle class="node" data-n="${n}" cx="${POS[n][0]}" cy="${POS[n][1]}" r="11" fill="${fill}"/>`;
  });
  svg.innerHTML = s;
  svg.querySelectorAll('.node').forEach(el => {
    el.addEventListener('click', () => {
      color[el.dataset.n] = sel; render();
      setStatus('Color all 7 points. Avoid same-color neighbors.', '');
    });
  });
}
function setStatus(t, cls) { const e = document.getElementById('status'); e.textContent = t; e.className = 'status ' + cls; }

function check() {
  const uncolored = NAMES.filter(n => color[n] === undefined).length;
  if (uncolored) { setStatus(fmt('%uncolored% point(s) still uncolored.', { uncolored: uncolored }), 'bad'); return; }
  const bad = badEdges();
  const used = new Set(NAMES.map(n => color[n])).size;
  if (bad.length === 0) setStatus(fmt('✓ Proper coloring with %used% colors! (3 is impossible — you used a 4th.)', { used: used }), 'ok');
  else setStatus(fmt('✗ %length% edge(s) clash. With only 3 colors this can never be fixed.', { length: bad.length }), 'bad');
}

// Brute force: try to k-color; return a valid assignment or null.
function tryColor(k) {
  const adj = {}; NAMES.forEach(n => adj[n] = []);
  EDGES.forEach(([a, b]) => { adj[a].push(b); adj[b].push(a); });
  const c = {};
  function go(i) {
    if (i === NAMES.length) return true;
    const v = NAMES[i];
    for (let col = 0; col < k; col++) {
      if (adj[v].every(u => c[u] !== col)) { c[v] = col; if (go(i + 1)) return true; delete c[v]; }
    }
    return false;
  }
  return go(0) ? c : null;
}

function auto() {
  // Show that 3 fails and 4 works.
  if (tryColor(3)) { setStatus('Unexpected: 3 worked.', 'ok'); return; }
  const four = tryColor(4);
  palette = [0, 1, 2, 3]; buildPalette();
  NAMES.forEach(n => color[n] = four[n]);
  render();
  setStatus('No 3-coloring exists — a 4th color (Slate) was required. So the plane needs ≥ 4.', 'ok');
}

document.getElementById('check').addEventListener('click', check);
document.getElementById('auto').addEventListener('click', auto);
document.getElementById('reset').addEventListener('click', () => {
  NAMES.forEach(n => delete color[n]); palette = [0, 1, 2]; sel = 0;
  buildPalette(); render(); setStatus('Color all 7 points. Avoid same-color neighbors.', '');
});
buildPalette(); render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hadwiger-nelson/Content licensed under CC BY-NC 4.0.