The four-colour theorem

Draw any map of regions on a flat sheet. Colour it so that no two regions sharing a border get the same colour. You never need more than four colours.

Why it is cool

The claim was made in 1852 and looks like it should have a short proof. It does not. It resisted every attempt for 124 years, and the proof that finally landed in 1976 — by Appel and Haken — needed a computer to check hundreds of cases, the first major theorem settled that way. A later proof by Robertson, Sanders, Seymour and Thomas cut the case list to 633 configurations and is still computer-checked. The theorem is easy to state, easy to believe, and hard to prove — and it changed what mathematicians accept as a proof.

The mechanism

First, turn the map into dots and lines. Put a dot in each region, and join two dots with a line if their regions share a border. That drawing is a planar graph: it can be drawn on a flat sheet with no lines crossing. Colouring the map is now colouring the dots so that no line joins two dots of the same colour.

Why four might be needed: a region surrounded by a ring of five regions, each touching its two ring neighbours, cannot be done in three. Two colours alternate around the ring, but five is odd, so the ring needs a third, and the centre touches all of them and needs a fourth.

Why five is never needed is the hard part, and the shape of the argument is this. Suppose some map needed five colours, and take the smallest such map. Counting dots, lines and faces on a flat sheet shows every planar graph has some dot with at most five lines out of it. A dot with three or four lines can be deleted, the rest coloured with four colours by minimality, and the dot put back with a spare colour — Kempe showed this in 1879. That leaves the five-line case, where his argument fails. The modern proofs replace "one dot" by a list of small local patterns and prove two things by computer: every planar graph contains at least one pattern from the list — the list is unavoidable — and each pattern can be recoloured away — each is reducible. So a smallest counterexample cannot contain any of them, and it cannot avoid all of them. It does not exist.

In one breath

Regions become dots, borders become lines, and the drawing never crosses itself. Some maps genuinely need four colours. None needs five: a smallest five-colour map would have to contain one of a finite list of local patterns, and every pattern on the list can be recoloured with four. Both halves are checked by machine.