Introduction

In 1852 a young Englishman named Francis Guthrie was coloring a map of the counties of England and noticed something odd: he never seemed to need more than four colors to keep every pair of bordering counties distinct. Was four always enough, for any map you could ever draw?

The rule is tiny. Color the regions of a flat map so that any two regions sharing a border get different colors. (Touching at a single point doesn't count.) Try it on a globe, a subway map, a cartoon of imaginary kingdoms — four colors always seem to suffice.

That innocent observation resisted proof for 124 years. And when the answer finally came in 1976, it arrived in a way that split the mathematical world: the first major theorem whose proof no human could fully check by hand.

Color a Map

Here is a small map. Click a region to cycle it through four colors. Your goal: make sure no two regions that share a border end up the same color. One of the layouts genuinely needs all four — three will never be enough.

<p class="hint">Click a region to cycle its color (gray means uncolored). Make every pair of regions that share a <b>border</b> differ. In this map all four regions touch each other, so it genuinely needs the 4th color — three can never work. Checking is instant; finding a coloring is the search.</p>
<svg id="map" viewBox="0 0 300 215" role="img" aria-label="A small map to color"></svg>
<div class="status" id="status">Color the regions, then check.</div>
<div class="btns">
  <button id="check" type="button">Check borders</button>
  <button id="solve" type="button">Solve it</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 .7rem; line-height: 1.45; }
#map { width: 100%; max-width: 360px; height: auto; display: block; margin: .3rem 0;
       border: 1px solid #cdd9e3; border-radius: 10px; background: #f6f9fb; }
#map path { stroke: #1d3557; stroke-width: 1.8; cursor: pointer; transition: fill .12s; }
#map text { font: 700 14px system-ui, sans-serif; fill: #1d3557; pointer-events: none; }
.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] ?? ''));
// The Four Color Theorem (Appel & Haken, 1976): every planar map can be colored
// with 4 colors so that no two regions sharing a border match. Here the player
// colors a small map. CHECKING a coloring is a quick scan of every border;
// FINDING one is a backtracking search. This map is the smallest hard case: four
// regions, each touching the other three (a "K4"), so 3 colors are impossible — exactly 4 are required.

const PALETTE = ['#c9ccd1', '#e63946', '#2a9d8f', '#f4a261', '#4361ee']; // index 0 = uncolored
// A big triangle T(150,20) L(25,195) R(275,195) with a small inner triangle.
// A, B, C are the three outer slices; D is the inner region. Every pair shares a border.
const REGIONS = {
  A: { d: 'M150 20 L25 195 L110 165 L150 115 Z', cx: 88,  cy: 128 },
  B: { d: 'M150 20 L150 115 L190 165 L275 195 Z', cx: 192, cy: 110 },
  C: { d: 'M25 195 L275 195 L190 165 L110 165 Z', cx: 150, cy: 184 },
  D: { d: 'M150 115 L110 165 L190 165 Z',         cx: 150, cy: 152 },
};
// Shared borders. All four are mutually adjacent (complete graph on 4 nodes).
const ADJ = {
  A: ['B', 'C', 'D'],
  B: ['A', 'C', 'D'],
  C: ['A', 'B', 'D'],
  D: ['A', 'B', 'C'],
};
const NAMES = Object.keys(REGIONS);
const color = {}; NAMES.forEach(n => color[n] = 0); // 0 = uncolored

const svg = document.getElementById('map');
function render() {
  svg.innerHTML = '';
  for (const n of NAMES) {
    const p = document.createElementNS('http://www.w3.org/2000/svg', 'path');
    p.setAttribute('d', REGIONS[n].d);
    p.setAttribute('fill', PALETTE[color[n]]);
    p.addEventListener('click', () => { color[n] = (color[n] + 1) % PALETTE.length; render(); setStatus('Color the regions, then check.', ''); });
    svg.appendChild(p);
    const t = document.createElementNS('http://www.w3.org/2000/svg', 'text');
    t.setAttribute('x', REGIONS[n].cx); t.setAttribute('y', REGIONS[n].cy + 4);
    t.setAttribute('text-anchor', 'middle'); t.textContent = n;
    svg.appendChild(t);
  }
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

// A coloring is valid iff every region is colored and no shared border joins equal colors.
function conflicts(col) {
  const bad = [];
  for (const a of NAMES) for (const b of ADJ[a]) {
    if (a < b && col[a] !== 0 && col[a] === col[b]) bad.push(a + '-' + b);
  }
  return bad;
}
function check() {
  if (NAMES.some(n => color[n] === 0)) { setStatus('Some regions are still gray.', 'bad'); return; }
  const bad = conflicts(color);
  if (bad.length === 0) setStatus('✓ Valid! No two neighbors share a color.', 'ok');
  else setStatus(fmt('✗ Border %v% has matching colors. Keep going.', { v: bad[0] }), 'bad');
}

// Backtracking solver over the 4 real colors (1..4). Tries colors in order and
// backtracks on conflict, counting how many assignments it tested.
function solve() {
  const assign = {}; let steps = 0;
  const ok = (n, c) => ADJ[n].every(m => assign[m] !== c);
  function bt(i) {
    if (i === NAMES.length) return true;
    const n = NAMES[i];
    for (let c = 1; c <= 4; c++) { steps++;
      if (ok(n, c)) { assign[n] = c; if (bt(i + 1)) return true; delete assign[n]; }
    }
    return false;
  }
  if (bt(0)) {
    NAMES.forEach(n => color[n] = assign[n]); render();
    const used = new Set(Object.values(assign)).size;
    setStatus(fmt('Solved with %used% colors after %steps% tries.', { used: used, steps: steps }), 'ok');
    console.log('Coloring:', JSON.stringify(assign), '| colors used:', used, '| tries:', steps);
  } else setStatus('No 4-coloring exists (impossible for a planar map!).', 'bad');
}

document.getElementById('check').addEventListener('click', check);
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click', () => { NAMES.forEach(n => color[n] = 0); render(); setStatus('Color the regions, then check.', ''); });
render();
Result
Console

Notice the asymmetry. Checking a finished map is effortless: walk over each border and confirm the two sides differ. Finding a valid coloring by hand can take real searching — press Solve it and the computer backtracks through color choices until every border is satisfied. For a handful of regions that's quick; as maps grow, the number of colorings to consider can blow up.

The Real Complexity

What exactly was proven, and what stays hard?

  • It's settled — and four is the magic number. In 1976 Kenneth Appel and Wolfgang Haken at the University of Illinois proved that every planar map can be colored with four colors. Their strategy: show that any map must contain one of an unavoidable set of configurations, and that each one is reducible — a four-coloring of the rest always extends to it.
  • A computer checked 1,936 cases. That unavoidable set was huge. Verifying every configuration by hand was hopeless, so they wrote programs that ground through roughly 1,936 cases (later refined to 1,482). It was the first famous theorem whose proof leaned essentially on a computer — and many mathematicians were uneasy about a proof they couldn't read in full.
  • Doubt, then confirmation. In 1997 Robertson, Sanders, Seymour and Thomas produced a cleaner computer proof, and in 2005 Georges Gonthier verified the whole thing inside the Coq proof assistant, machine-checked end to end.
  • The cousin is brutally hard. Asking whether a map needs only three colors — or coloring an arbitrary, non-planar graph — is NP-complete. Four colors for planar maps is a gift; three colors is a wall.

That is the twist: the headline result is proven and reassuring — four always works — yet it sits one notch away from graph coloring, which is as hard as anything in P vs NP.

Where It Matters

"Give every item a label so that things in conflict never share one" is one of the most common shapes a real problem takes, and map coloring is its friendly face:

  • Scheduling: exams or meetings that share a participant must land in different time slots — colors are the slots.
  • Radio and mobile frequencies: nearby transmitters need different channels to avoid interference, exactly like bordering regions.
  • Compilers (register allocation): variables alive at the same moment can't reuse the same CPU register; compilers color a conflict graph to assign them.
  • Seating, teams, and conflict resolution: any "keep these two apart" rule is an edge waiting to be colored.

Learn why four colors suffice for maps and you've met graph coloring — the engine under graph coloring, scheduling and a host of real allocation problems.

Conclusion

The Four Color Theorem hides a double surprise. Mathematically, the answer is generous: four colors are always enough for any flat map, no exceptions, finally proven by Appel and Haken in 1976. But the way it was proven broke new ground — a computer marched through nearly two thousand cases that no person could check alone, forcing mathematics to ask what a proof even is.

So the next time you idly color in a map and never reach for a fifth crayon, remember: you are touching a question that took 124 years, a computer, and eventually a fully machine-checked proof to settle — and whose three-color sibling, like graph coloring, remains genuinely hard.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/four-color-theorem/Content licensed under CC BY-NC 4.0.