The Four-Color Theorem: Why Maps Need Only Four Colors

My daughter spent a rainy Saturday afternoon coloring a map of a made-up island. Twelve regions, a coastline, a mountain range that split the middle into three pieces. She had a box of sixty-four crayons open on the floor and used exactly four of them, then looked at the page and said the thing that turns a craft project into an argument: I think four colors is always enough. I could not just say yes.

The claim she had discovered is the four-color theorem, and it is one of the strangest results in mathematics. The sentence is short enough for a nine-year-old to state and check on a small map. The proof behind it took one hundred and twenty-four years, a famous mistake, and eventually a computer that was allowed to be part of the mathematics. It is also the rare theorem where explaining the answer teaches more than the answer itself.

What the theorem actually says

The rule is about neighbors. Two regions are neighbors when they share a stretch of border, not when they happen to meet at a single point. That distinction carries the whole idea. Three regions can meet at one corner, and all three may be the same color, because no pair of them shares an edge. The coloring rule bites only when two regions run alongside each other.

So the theorem says: take any flat map, chop it into regions however you like, and you can assign one of four colors to each region so that no two neighbors match. Not five. Not six. Four, for every map anyone has ever drawn and every map anyone ever will. Regions do not have to be pretty or equal, and the map does not have to come from real geography. The shapes only have to join edge to edge, which is the same condition that makes a tiling work, and a good place to start is our tessellation guide.

The flat part matters too. Bend the same map onto the surface of a donut, and four colors stop being enough: some maps on that surface need seven. The plane is generous, and nobody expected it to be.

Five colors are easy, and four are not

Here is the difference in one paragraph. Every flat map has at least one region with five or fewer neighbors. Find that region, set it aside, color the rest of the map, and put it back: it has at most five neighbors, so six colors always leave it a free option. That argument gives six colors, and it takes a beginner about ten minutes. Trim it to five and you need a cleverer move, involving chains of regions that alternate between two colors so you can swap a whole chain at once and free up the color you want.

That chain trick is where the century went. Alfred Kempe published a proof in 1879 using exactly this kind of swapping, and the mathematical world accepted it. It stood for eleven years. In 1890 Percy Heawood found the gap: in one arrangement two chains cross so that the first swap undoes the second, and Kempe's tidy exchange does not survive contact with every case.

Kempe's argument was not nonsense. It proved that five colors are enough, which is why the five-color theorem is a standard homework problem and the four-color theorem is not. What failed was a step that looked obvious on the page, and the reason it lasted eleven years is uncomfortable: nobody went looking for the flaw until someone had a reason to. Telling a child that story is more useful than telling them to check their work, because it shows what happens when a proof is trusted for its reputation rather than its details, which is the habit underneath logic and reasoning.

The proof that had to be handed to a machine

By the 1970s the search had turned into a hunt for a finite list. The strategy was to prove two things about a collection of small patterns: at least one of them must appear in any map, and any map containing one of them can be shrunk without changing the answer. Build such a list and the theorem follows, because a map that needed five colors could be shrunk forever, which is impossible.

The problem was the size of the list. Kenneth Appel and Wolfgang Haken, working at the University of Illinois, assembled an unavoidable set of 1,936 configurations and checked each one with a computer program, running for more than a thousand hours of machine time. The discharging half of the argument went into the Illinois Journal of Mathematics in 1977, and the reducibility half followed with John Koch, a graduate student who did much of the case checking and is credited on the second paper (Appel & Haken, 1977). The announcement made the local news, and the mathematics department put a postmark reading Four colors suffice on its outgoing mail for years afterward.

Not everyone was pleased. A proof no human being could read from start to finish felt like a different kind of object, and some mathematicians treated it as a challenge rather than a result.

A smaller case list, and the machine stayed

The improvement came in 1996, when Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas produced a new proof whose unavoidable set contained 633 configurations, a fraction of the original. Robin Thomas wrote up the state of the question two years later for the Notices of the American Mathematical Society, describing the 633 configurations and the algorithm that checks a map quickly once the list is in hand (Thomas, 1998). The computer stayed in the room. It just had less to do, and the case list was small enough that parts of the work could be inspected by eye.

A second shift came in 2005, when Georges Gonthier used a proof assistant called Coq to machine-check the argument. This is a different guarantee from the 1977 one: instead of trusting a program to test cases correctly, the logic of the proof is verified by a separate checker. The people involved read like a chapter of famous mathematicians.

Line the four attempts up and they follow one shape: Kempe by hand in 1879 and wrong, Appel and Haken in 1977 with a machine nobody could watch, the 1996 proof small enough to audit, and the 2005 rebuild checked by a separate program. The theorem never moved. What moved was how much of each argument a reader was being asked to take on faith.

How to run this at the kitchen table

You do not need the proof to use the theorem. Draw an island with eight or ten regions, hand over four colors, and let your child try to force a fifth. Most attempts fail in a way that teaches something. The usual stall is a region ringed by five neighbors: those five cannot all touch each other along borders, so two of them are free to share a color. Finding that pair is the whole game.

A useful habit is to color the busiest region first, the one with the most neighbors, and work outward. Kids who color the biggest area first spend the last ten minutes repainting. If the regions are quadrilaterals and triangles, counting sides helps too, and our polygon guide covers the basic vocabulary.

Then admit the limits. Two children coloring ten maps have not proved anything about the ten billionth map. What they have done is test a claim, watch it survive, and learn the difference between a pattern that holds and a reason that explains why it must.

What the theorem is really teaching

The four-color theorem is a good answer to the question children ask about mathematics in general: why would anyone bother proving something that is already obvious on every map they have ever seen? The theorem shows that a claim can be simple to state, true in every example you can reach, and still hide a trap that held up the best minds in the field for over a century. It also shows that a proof can be strange, large, assisted by a machine, and still count. When my daughter finally stopped coloring and asked whether we had proved it ourselves, the answer was no, and that was the best part of the afternoon.