Introduction

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.

Try It

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.

<!-- Hadwiger-Nelson problem demo: color a 5x5 integer grid with 4 colors so no two unit-distance points share a color. -->
<p class="hint">Click any dot to cycle through 4 colors (gray = uncolored). Try to color all 25 points so that <b>no two dots exactly 1 unit apart share the same color</b>. Then press Check to find any conflicts.</p>
<div id="canvas-wrap">
  <canvas id="plane" width="340" height="340" title="Interactive coloring grid"></canvas>
</div>
<div class="status" id="status">Click dots to color them, then press Check.</div>
<div class="btns">
  <button id="btn-check" type="button">Check coloring</button>
  <button id="btn-reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Hadwiger-Nelson: what is the minimum number of colors to paint the plane so no two points */
/* at distance exactly 1 share a color. */
const COLS = ['gray', '#e63946', '#2a9d8f', '#e9c46a', '#457b9d'];
const NCOLORS = 4; /* We allow 4 colors to explore the constraint. This small grid is actually 4-colorable; impossibility requires a larger unit-distance graph. */
const GRID = 5; /* 5x5 integer grid (points at coordinates 0..4 in both axes) */
const CELL = 60; /* pixels between adjacent grid points (= 1 unit in the problem) */
const PAD = 30;
const colors = {}; /* maps point key -> color index (0 = uncolored, 1..4 = the four colors) */
let conflictPairs = [];

/* Collect all pairs of grid points at exactly distance 1 (horizontal/vertical neighbors only on integer grid). */
function unitPairs() {
  const pairs = [];
  for (let r1 = 0; r1 < GRID; r1++) for (let c1 = 0; c1 < GRID; c1++)
    for (let r2 = 0; r2 < GRID; r2++) for (let c2 = 0; c2 < GRID; c2++) {
      if (r1 === r2 && c1 === c2) continue;
      const dx = c2 - c1, dy = r2 - r1;
      if (dx * dx + dy * dy === 1) pairs.push([r1, c1, r2, c2]);
    }
  return pairs;
}
const ALL_UNIT_PAIRS = unitPairs();

function key(r, c) { return r + ',' + c; }
function cx(col) { return PAD + col * CELL; }
function cy(row) { return PAD + row * CELL; }

/* Redraw the canvas: conflict edges first, then all dots. */
function draw() {
  const canvas = document.getElementById('plane');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  /* Draw conflict edges first so dots render on top. */
  const conflictSet = new Set();
  for (const [r1, c1, r2, c2] of conflictPairs) {
    conflictSet.add(key(r1, c1));
    conflictSet.add(key(r2, c2));
    ctx.strokeStyle = '#e63946';
    ctx.lineWidth = 2;
    ctx.setLineDash([4, 3]);
    ctx.beginPath();
    ctx.moveTo(cx(c1), cy(r1));
    ctx.lineTo(cx(c2), cy(r2));
    ctx.stroke();
    ctx.setLineDash([]);
  }

  /* Draw each dot with its assigned color; ring in red if in a conflict. */
  for (let r = 0; r < GRID; r++) for (let c = 0; c < GRID; c++) {
    const k = key(r, c);
    const colIdx = colors[k] || 0;
    const filled = colIdx > 0;
    ctx.beginPath();
    ctx.arc(cx(c), cy(r), 10, 0, 2 * Math.PI);
    ctx.fillStyle = filled ? COLS[colIdx] : '#c9ccd1';
    ctx.fill();
    if (conflictSet.has(k)) {
      ctx.strokeStyle = '#c92f3c';
      ctx.lineWidth = 3;
      ctx.stroke();
    } else {
      ctx.strokeStyle = filled ? COLS[colIdx] : '#adb1b8';
      ctx.lineWidth = 1.5;
      ctx.stroke();
    }
  }
}

/* On click, find the nearest dot and cycle its color. */
document.getElementById('plane').addEventListener('click', function(e) {
  const rect = this.getBoundingClientRect();
  const px = (e.clientX - rect.left) * (340 / rect.width);
  const py = (e.clientY - rect.top) * (340 / rect.height);
  let best = null, bestDist = 999;
  for (let r = 0; r < GRID; r++) for (let c = 0; c < GRID; c++) {
    const d = Math.hypot(px - cx(c), py - cy(r));
    if (d < bestDist) { bestDist = d; best = [r, c]; }
  }
  if (best && bestDist < 22) {
    const k = key(best[0], best[1]);
    colors[k] = ((colors[k] || 0) + 1) % (NCOLORS + 1);
    conflictPairs = [];
    setStatus('Click dots to color them, then press Check.', 'info');
    draw();
  }
});

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

/* Check every unit-distance pair; collect conflicts; update status and redraw. */
function check() {
  const uncolored = [];
  for (let r = 0; r < GRID; r++) for (let c = 0; c < GRID; c++)
    if (!colors[key(r, c)]) uncolored.push(key(r, c));
  if (uncolored.length > 0) {
    setStatus(i18nFmt('%n% dot(s) are still uncolored — color all of them first.', { n: uncolored.length }), 'info');
    conflictPairs = [];
    draw();
    return;
  }
  conflictPairs = ALL_UNIT_PAIRS.filter(([r1, c1, r2, c2]) =>
    (colors[key(r1, c1)] || 0) > 0 &&
    colors[key(r1, c1)] === colors[key(r2, c2)]
  );
  if (conflictPairs.length === 0) {
    setStatus('No conflicts! This grid allows a valid 4-coloring. De Grey’s impossibility needs a more complex unit-distance graph.', 'ok');
  } else {
    setStatus(i18nFmt('%n% unit-distance conflict(s) highlighted in red — fix them to find a valid 4-coloring.', { n: conflictPairs.length }), 'bad');
  }
  draw();
}

document.getElementById('btn-check').addEventListener('click', check);
document.getElementById('btn-reset').addEventListener('click', function() {
  for (const k of Object.keys(colors)) delete colors[k];
  conflictPairs = [];
  setStatus('Click dots to color them, then press Check.', 'info');
  draw();
});

draw();
Result
Console

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 Real Complexity

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.

Where It Matters

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 Z\mathbb{Z} so that no two integers at distance dd share a color) is classical and fully solved — but the jump to R2\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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/chromatic-number-of-the-plane/Content licensed under CC BY-NC 4.0.