Mathematics, plainly explained

The Map Coloring Theorem, Explained

Four colors are enough for any map in the world - that's the map coloring theorem, more formally known as the Four Color Theorem. A claim short enough to fit in one sentence, yet it took 124 years and, in the end, a computer to prove. Here's the full story: what the theorem actually says, why it resisted proof for so long, how the proof finally succeeded - and where it breaks down.

Cartographer turns this exact theorem into a game - 120 hand-drawn islands, the first 10 free.

What Does the Map Coloring Theorem Say?

The map coloring theorem is one of the most compact statements in mathematics: any map can be colored with at most four colors so that no two neighboring regions ever share the same color. It doesn't matter how many countries the map has or how tangled its borders are - four colors are always enough.

Two words in that sentence carry more weight than they first appear to. Two regions count as neighboring only if they share an actual border line - a single touching point doesn't count. And every region has to be connected: a country made of two separate pieces doesn't count as one region. Both restrictions look like fine print, but they're the reason the theorem is provable at all - and, as described further down, the reason it doesn't cleanly apply to some real-world maps.

Mathematically, the map coloring theorem is really a statement about graphs, not maps: any map can be translated into what's called a planar graph, turning each region into a point and each shared border into a connecting line. The theorem then says: any planar graph can be colored with at most four colors so that two points joined by a line never share a color. Maps are just the most intuitive version of this more abstract, more general statement.

Why Isn't the Map Coloring Theorem Obvious?

That three colors sometimes aren't enough is easy to show in seconds: three regions that all touch each other need three different colors. It would be natural to guess that this trick keeps going forever - five mutually touching regions for five colors, six for six, with no upper limit at all. But that's not what happens. Past a certain point, the plain geometry of a flat surface makes it impossible for arbitrarily many regions to all touch each other - and that point turns out to be four. The map coloring theorem is the claim that this limit doesn't just hold for small, simple maps, but for every map that could ever be drawn, no matter how complicated. That jump from "true in every case examined so far" to "true in every conceivable case, forever" is what turns an observation into a theorem - and what turned this particular theorem into a 124-year-old open problem.

The History of the Map Coloring Theorem

The conjecture came from a student: in 1852, Francis Guthrie, a Londoner, was coloring a map of the English counties and noticed he never needed more than four colors, no matter how he drew the borders. His brother Frederick brought the question to the mathematician Augustus De Morgan, who passed it along the very same day - October 23, 1852 - in a letter to William Rowan Hamilton. Hamilton wasn't interested, but De Morgan kept raising the question and carried it through London's mathematical circles.

In 1878, Arthur Cayley brought the still-unsolved question before the London Mathematical Society. A year later, the lawyer and amateur mathematician Alfred Kempe published a proof that stood unchallenged for eleven years. Kempe's method - known today as Kempe chains - is itself elegant mathematics: take two of the four colors and trace the connected chain of regions that alternate between only those two colors. If that chain can be cut at some point, the two colors on part of the chain can simply be swapped without creating a conflict anywhere - freeing up the fourth color exactly where it was needed. Peter Guthrie Tait attempted his own proof in parallel, in 1880.

In 1890, Percy Heawood found the gap in Kempe's argument: for certain configurations, two chains can't be swapped independently of each other without opening up a new conflict somewhere else. Kempe's proof was refuted - the map coloring theorem was open again. Out of the wreckage, Heawood salvaged the Five Color Theorem: using Kempe's chain technique, it's possible to prove by hand, completely, that five colors are always enough for any map. Only the final, decisive step from five down to four remained unproven. In 1891, Julius Petersen also refuted Tait's 1880 attempt. For nearly another century, the map coloring theorem remained an open conjecture.

1,476 map patterns are better left to a computer. A single island, on the other hand, is easy to solve by hand - Cartographer has 120 of them waiting.

Try it for free

The 1976 Proof: Computer versus Pen and Paper

The breakthrough finally came in 1976, from Kenneth Appel and Wolfgang Haken at the University of Illinois - but not on paper. Their strategy follows a pattern Kempe had already been reaching for: assume there's a map that violates the theorem, and pick the smallest possible such counterexample among all of them. Then show that this minimal counterexample is impossible - and therefore every larger one is impossible too, since a larger one could always be reduced to a smaller one.

The trick is finding an unavoidable set of reducible configurations: a list of map patterns, at least one of which must appear in every minimal counterexample (unavoidable), and each of which can individually be shown to be impossible (reducible). To find that list at all, Appel and Haken used what's called the discharging method: every region is assigned a starting charge based on how many neighbors it has, and that charge gets redistributed between neighboring regions according to a fixed set of rules - not unlike an electrical network. What's left at the end reveals which regions must necessarily belong to one of the reducible configurations.

In the end, 1,936 configurations remained, later trimmed to 1,476 - far too many to check by hand. Appel and Haken had a computer run for roughly 1,200 hours. The result: the map coloring theorem holds. But no mathematician could trace the proof from start to finish by hand anymore - it wasn't too hard for a person, just too long.

“Four colors suffice.”Postmark used by the University of Illinois mathematics department for years after 1976

That sparked real controversy in the mathematical community. Was a proof that could no longer be read, only run, still a proof at all? In 1989, Appel and Haken published a complete, roughly 400-page write-up. In 1997, Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas trimmed the necessary case count down to 633 - the proof got simpler, but stayed computer-assisted. The final reassurance came only in 2005: Georges Gonthier and Benjamin Werner had the entire proof checked once more by a so-called proof assistant named Coq - software that formally verifies every single logical step, leaving no room for doubt at all.

Why No One Can Check the Proof by Hand

The difference between the map coloring theorem and the Five Color Theorem shows what's really going on here. The Five Color Theorem - the weaker claim that five colors always suffice - can be proven by hand in full, using Kempe's chain technique, in a few pages, followable by any math student. The map coloring theorem, by contrast, leaves the discharging method with a number of remaining cases that's simply too large for a human mind - not too complicated, just too much. That was something entirely new in 1976: the first major mathematical proof to depend essentially on a computer. Today that's routine in many corners of mathematics, but the map coloring theorem was the case that first forced the field to seriously ask what a proof even is, once no human can fully check it anymore.

Where the Map Coloring Theorem Breaks Down

The map coloring theorem describes pure geometry - and once real countries and real borders enter the picture, it shows its limits too.

The Map Coloring Theorem in Practice: Graph Coloring

The map coloring theorem itself is a statement about maps and planar graphs - but the underlying idea, coloring a graph so that connected points never share a color, is its own, much broader tool in computer science known as graph coloring. In scheduling, for instance, events become points, and two events get connected whenever they can't overlap - say, because the same instructor teaches both. A valid coloring then corresponds to a schedule with no conflicts, with each color standing for a time slot. Register allocation in compilers, where a program's variables have to be distributed across a limited number of processor registers, is fundamentally the same problem. Unlike maps, though, these graphs are usually not planar - so the four-color limit doesn't apply there, and noticeably more colors are often required. What survives is the idea that the map coloring theorem made famous.

Try the Map Coloring Theorem Yourself

Cartographer turns the map coloring theorem into a game: 120 hand-drawn island maps, all governed by exactly this one rule - neighbors can never share a color. The first 10 maps are free, and there's a playable demo right in your browser.

Play the demo

Frequently Asked Questions About the Map Coloring Theorem