Why Three Colours Are Never Enough

Draw a country. Draw its neighbours. Keep going until you have a map you are pleased with, then colour it in — with one rule.

Two countries that share a border must not be the same colour. Touching at a single point does not count; two countries need a proper stretch of border between them before they have to differ.

Now try to use as few colours as you can. Two, if you can manage it. Three if you cannot.

You are going to run out at three. And the reason is one particular arrangement of four countries, which you can rule out completely without trying a single colour.

Sometimes two colours are plenty

Start where it is generous. Draw four countries in a ring, each touching the two beside it, like four slices of a cake.

Colour them round the ring: red, blue, red, blue. The first and third never touch, so they may share. Two colours, done.

Now a ring of five. Go round the same way — red, blue, red, blue — and the fifth country is stuck between a blue and the red you started with. It needs a third colour.

That is worth pausing on. Nothing about a five-country ring is bigger or more complicated than a four-country ring. It is odd rather than even, and going round an odd ring you always arrive back where you began on the wrong foot.

Where three runs out

Now the arrangement that beats three colours, and it is smaller than you would guess. It needs only four countries.

Draw three countries meeting in the middle of the page, like three slices sharing a centre. Now draw a fourth as a small round country sitting right on the spot where the other three meet, so that it pushes them apart and shares a border with all three.

Look at what you have. Every one of the four shares a border with each of the other three. There is no pair anywhere on that map that fails to touch.

So all four need different colours. Not "it is hard to do with three" — three is impossible, and you can see why in one line: with only three colours in the tin, two of the four countries must end up the same colour, and any two of them share a border.

Every country on that island borders all three others, so the island needs four colours. Counted properly, there are 24 ways to colour it with four, which is simply the four colours arranged in every possible order, because each country takes one and no two may match.

With three colours there are no ways at all. Not few. None.

Which maps need the fourth colour

You now have two useful facts: odd rings are awkward, and a country in the middle touches everything around it. Put them together and you can predict a map before you colour it.

The pattern is the odd rings. A ring with an even number of countries takes two colours, so the middle country can have the third and everybody is satisfied. A ring with an odd number of countries already needs three all by itself, so the country in the middle — which borders every one of them — has to reach for a fourth.

So is four always enough?

This is where the story stops being tidy.

Nobody has ever drawn a flat map that needs five colours. People have been trying since 1852, when a student colouring a map of England noticed that he never seemed to need more than four, and asked why.

Twenty-seven years later, in 1879, a lawyer called Alfred Kempe published a proof that four colours are always enough. It was accepted. It stood for eleven years. Then in 1890 Percy Heawood read it closely and found a hole in it that could not be patched.

Heawood did rescue something. He showed that five colours are always enough, which is a real result and a good deal easier to establish. But the gap between four and five stayed open.

It stayed open until 1976. That is 124 years after the question was first asked. Kenneth Appel and Wolfgang Haken settled it by reducing every possible map to a list of nearly two thousand awkward shapes, then getting a computer to check them one at a time. The checking took over a thousand hours of computer time, and no person has ever read the whole of that part by hand.

The tempting wrong answer

Here is the reasoning almost everybody tries first. It is worth seeing why it fails, because it is a good idea that does not go far enough.

You cannot fit five countries on a flat map so that all five touch each other. Four is the limit — try adding a fifth that borders all the others and you will find it walled out every time. So surely four colours must be enough?

No. And this is the whole difficulty.

Needing five colours does not require five countries that all touch. A map can force a fifth colour through a long chain of ordinary neighbours, none of them touching more than a few others, where the trouble only appears once you have coloured half the map and painted yourself into a corner somewhere far away.

That is roughly the shape of the gap in the 1879 proof, and it is why the question survived 124 years instead of an afternoon.

Draw your worst map. Make it as tangled as you can manage, with long thin countries winding round each other, and then colour it. You will not need five. Nobody ever has — and saying so with certainty took longer than most of the countries on your map have existed.