Map maker / Guides
Map coloring: why four colors are always enough
Color South America so no neighbors match. With four colors it's easy. With three, one small country makes it impossible.
Loading the coloring puzzle…
The question a student asked in 1852
Francis Guthrie was coloring a map of the counties of England when he noticed four colors seemed to be enough to keep every pair of neighboring counties different. He asked whether that was true of every possible map. It took 124 years to answer.
Why three isn't enough
Three colors fail as soon as a map has a region surrounded by an odd number of neighbors that form a ring. In South America, Paraguay borders Brazil, Bolivia and Argentina, and those three all border each other. That's four countries that all touch each other, so they need four different colors. Switch the puzzle above to three colors and the algorithm hits the wall there. (Brazil, which borders ten countries, is the busiest node, but the problem is the tight cluster, not the number of neighbors.)
Why five is never needed
Proving that four always suffice is famously hard. Proving that five suffice is short: Percy Heawood did it in 1890. In any flat map there's always some region with five or fewer neighbors (a consequence of Euler's formula). Remove it, color the rest, put it back, and at worst you can swap two colors in a chain to free one up. The four color version needs the same idea pushed much further. Kenneth Appel and Wolfgang Haken finished it in 1976 by having a computer check 1,936 unavoidable configurations, which was controversial because no person could verify every case by hand.
How the algorithm above chooses
The step-through uses a greedy method called DSATUR (Brélaz, 1979): always color next the country whose neighbors already use the most different colors, and give it the lowest color still free. It isn't guaranteed to find a four-coloring on every map, but on real maps it nearly always does, and it's the same method behind the "Auto 4-color" button in the map maker. Try it on the whole world or the US states in one tap.
If working things out by hand appeals to you, ahaboo offers explainers you can manipulate directly, like dragging the Moon to understand why it has phases.
Does it matter for making maps?
For a clean political map, yes: four soft colors make borders readable without implying groupings. But when color carries meaning (a legend, data, membership) you choose colors for the message, not the minimum. Use the choropleth map maker for that.
Questions
What is the four color theorem?
Any map drawn on a flat surface can be colored with at most four colors so that no two regions sharing a border get the same color. Regions that only meet at a single point, like the Four Corners states, may share a color.
Who proved the four color theorem?
Kenneth Appel and Wolfgang Haken at the University of Illinois in 1976, after Francis Guthrie first posed the problem in 1852. Their proof relied on a computer checking 1,936 configurations, which made it the first major theorem proved with computer help. Georges Gonthier verified it with the Coq proof assistant in 2005.
Does the theorem work for real world maps?
Almost. Real maps break one assumption: countries in several pieces. Alaska must match the rest of the US, and Kaliningrad must match Russia. With such exclaves, more than four colors can occasionally be needed, although in practice four still works for today's world map.
Why do political maps usually use more than four colors?
For readability and meaning, not necessity. Cartographers often give neighbors strongly contrasting colors and keep a country the same color across editions. Four is the minimum, not a rule.