Why are four colors enough for any map?
Give somebody a blank map and four coloring pencils, with one rule: countries that share a border cannot share a color. It always works. Invent the most spiteful map you can, with long thin countries winding between each other, and four colors still cover it. Nobody in a hundred and seventy years has ever drawn a map that needs a fifth. The question is how anyone could possibly be certain.
The reason everybody offers is genuinely true, and it settles nothing. That gap swallowed one of the most admired arguments of the nineteenth century.
The rule, and the thing everybody notices first
Two countries count as neighbors when they share a stretch of border. Meeting at a single point does not count, which is why the four states around a corner in America can be colored in a way that would otherwise be impossible.
Color a few maps and a pattern appears. You keep needing a fourth pencil and you never need a fifth, and after a while you start wondering whether four is a rule rather than a coincidence.
That question got asked properly in 1852, roughly seven generations before you were born, by a student named Francis Guthrie. He was coloring the counties of England, which run about 500 km(310 mi) from top to bottom and are a genuine nuisance to color.
He noticed four always sufficed, could not prove it, and passed the puzzle to his brother. It reached a professor in London within the week and was not settled for another hundred and twenty-four years.
A statement like this — believed, unproved — is called a conjecture. Guthrie had one, and everybody who tried it agreed with him.
The obvious explanation, which is true
Here is what nearly everyone says next, and it is worth taking seriously. You cannot draw five countries on a flat sheet so that every one touches all four others.
Try it before reading on. Four is easy: draw a triangle of three countries and drop a fourth into the middle, touching all of them. Now attempt a fifth that reaches every one of the others without crossing anything. It cannot be done, and that is provable.
So no single knot of countries can ever demand five colors on its own. That is a real fact about flat surfaces, and it explains why nobody has ever stumbled on an obvious exception.
It just does not finish the argument, and seeing why is the whole point of this article.
Coloring is a problem about the whole map at once
Draw five countries in a ring, like slices of a pie. No three of them all touch each other — each one only borders the two beside it.
Now color it. Two colors would work for a ring of four, alternating around. With five, the alternation runs out when it comes back to the start, and you are forced to use a third.
Nothing in that ring is crowded. No three countries meet at once, yet you still needed more colors than the crowding suggested. How many countries touch simultaneously simply does not decide how many colors a map requires.
You do not run out of colors where the map is busy. You run out somewhere else entirely, because of a choice you made three countries ago.
That is why the flat-surface fact settles nothing on its own. It rules out one way of being forced into a fifth color, and coloring can trap you in ways that have nothing to do with any single crowded spot.
The argument that stood for eleven years and was wrong
In 1879 Alfred Kempe, a London lawyer who did mathematics in the evenings, published an argument that appeared to settle it. Mathematicians checked it, admired it, and moved on. Kempe was elected to the Royal Society.
His method was clever. Suppose a map existed that needed five colors, and suppose you took the smallest such map. He showed that every map must contain at least one of a short list of small arrangements, then argued that each arrangement could be recolored to save a color.
A demonstration like that, one that leaves no possible exception anywhere, is called a proof, and a statement with a proof behind it becomes a theorem. For eleven years this was the four-color theorem.
Then in 1890 Percy Heawood examined one of Kempe’s recoloring arguments closely and produced a map where it failed. Two of Kempe’s color swaps interfered with one another, undoing each other’s work.
One example was sufficient. A counterexample is a single case that a claim cannot survive, and Heawood had one. The theorem collapsed back into a conjecture and stayed there for most of a century.
Heawood was gracious about it, and he salvaged something real: Kempe’s method, used carefully, does prove that five colors are always enough. The gap between five and four took another eighty-six years.
The proof nobody could read
Kempe’s plan was sound even though his execution was not. You find a list of small patches of map — a particular arrangement of a few countries and their neighbors, which mathematicians call a configuration. Then you prove two things.
Every possible map, however large or peculiar, must contain at least one patch from your list. And every patch on your list can be recolored to free up a color. Together, those two facts leave no room for a map that needs five.
In 1976, at the University of Illinois, Kenneth Appel and a colleague assembled such a list. It contained 1,936 configurations, which is rather more than a short list, and each one had to be checked separately.
The checking time their computer needed, converted into days running without a break.
No person could do that. So a computer did it, running for more than a thousand hours, and the four-color theorem became the first famous result whose proof no human being could read from beginning to end.
Mathematicians argued about it for years, and the argument was a fair one. A proof is supposed to be something you can check yourself. Since then the list has been shortened, other teams have repeated the work independently, and a version has been checked by a second program written from scratch. Nobody doubts the answer now.
Try to break it
You will get stuck, and backing up will always rescue you. That is the honest experience of it: four colors are enough, but finding the arrangement can take patience, and no simple recipe hands you the answer.
A map made from straight lines alone is a special case with a neat surprise: two colors always work, because each new line flips every region on one side of it. Add a single curve and that guarantee is gone.
What the question was really about
The four-color theorem is not a useful fact. Mapmakers had four colors long before anyone proved anything, and they were never in any doubt.
What it demonstrates is how far apart nobody has found an exception and there is no exception really are. Kempe was a careful man, the mathematics world checked his work, and everybody was wrong for eleven years about something they were all certain of.
So the next time a pattern holds every single time you test it, you can enjoy the pattern and stay honest about it. A hundred maps that worked is a hundred maps that worked. It took a machine running for fifty days to turn that into a promise.
