Four Colours Are Enough
The puzzle
Colour the countries of any map drawn on a flat sheet so that no two countries sharing a border get the same colour. Countries are connected regions, and meeting at a single point does not count as sharing a border.
How many colours are always enough? And can you show four are sometimes necessary?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
For "sometimes necessary", find four countries that all border each other.
Hint 2
For "always enough" - that is the hard half, and it resisted proof for 124 years.
Show the answer Hide the answer
Four. Four are sometimes necessary, and four are always enough — though the second half took until 1976 and the first computer-assisted proof of a major theorem.
How to get there
Four are necessary: draw a central country with three others around it, each touching the centre and both its neighbours. All four border each other, so no two can share a colour.
Five are not needed, and that is the deep part. Kempe published a proof in 1879 that stood for eleven years before Heawood found the error - though Kempe's method, slightly repaired, does prove five colours suffice.
Appel and Haken settled it in 1976 by reducing the problem to 1,936 configurations and checking them by machine. It was the first major theorem whose proof no human could verify by hand, and the argument about whether that counts as a proof is still worth having. On a doughnut the answer is seven, and that case was settled long before the flat one.
The technique worth keeping
Separate "this many are necessary" from "this many are enough". The first needs one example and is usually easy; the second needs an argument covering every case and is usually where the difficulty lives.