The Four Color Theorem, Explained
After reading this you will know why four colors always suffice for a flat map, how to model a map as a graph, how the backtracking solver actually finds a coloring, and where the four color result stops holding.
What the theorem says and one map that hooks you
Take any map drawn on a flat sheet: countries, counties, whatever. Give each region a color so that two regions sharing a border get different colors. The four color theorem says four colors are always enough, no matter how tangled the map.
That is stronger than it sounds. You can draw maps that clearly need four. Picture one central region surrounded by three others, each touching the center and each touching its two neighbors. All four regions touch each other pairwise, so all four need distinct colors. Three colors fail. The surprise is that no map ever forces a fifth color, and proving that took 124 years.
Two regions that touch only at a single point do not count as neighbors. That rule matters. Without it you could build a pinwheel of thin slices meeting at one corner and demand arbitrarily many colors. "Sharing a border" means sharing a stretch of boundary with positive length.
From map to graph
The clean way to think about coloring is to throw away the shapes and keep only the touching relationships. Put one dot (a vertex) inside each region. Draw an edge between two dots whenever their regions share a border. The result is the adjacency graph of the map.
Because the map is flat and regions do not overlap, this graph is planar: you can draw it with no edges crossing. Coloring the map now means coloring the vertices so that no edge joins two vertices of the same color. The four color theorem in graph language:
Here \chi(G) is the chromatic number, the smallest number of colors that legally colors the graph G. The claim is that this number never exceeds 4 for planar graphs. The four-mutually-touching example above is the complete graph on 4 vertices, written K_4, and it has \chi = 4 exactly.
Why can you never force five? A hidden fact does the work: K_5, five vertices all joined to each other, cannot be drawn in the plane without a crossing. So five mutually bordering regions cannot exist on a flat map. That is necessary for the theorem but nowhere near sufficient, which is why the full proof is so hard.
Why five colors is easy and four is brutal
Five colors can be proved by hand in a page. The argument uses Euler's formula for planar graphs, V - E + F = 2 (the same relation you can check on the Platonic solids explorer). That formula forces every planar graph to contain a vertex with at most 5 neighbors. You remove such a vertex, color the rest by induction, then find a spare color for it, sometimes after swapping two colors along a chain. Clean and finite.
Four colors resisted that trick. The eventual 1976 proof by Appel and Haken reduced the whole problem to checking 1936 unavoidable configurations, and checking them needed a computer running for over 1000 hours. It was the first major theorem where a machine did an essential part of the reasoning, and mathematicians argued for years about whether a proof you cannot read by hand is really a proof. A cleaner 1997 version cut the list to 633 configurations, but it still needs a computer.
How the solver colors your map
The solver in this tool does not use the theorem's proof. It uses plain backtracking, the same depth-first search that cracks the N-queens puzzle. The theorem only promises a coloring exists; backtracking is how you find one.
Number the regions 1 to n. Try to color them in order. For region i, try color 1, then 2, then 3, then 4. Accept the first color that clashes with none of the already-colored neighbors, then move to region i+1. If all four colors clash, you are stuck: return to region i-1, advance it to its next untried color, and continue. The search halts when every region has a legal color.
The worst-case number of color assignments the search might try is bounded by 4^n for n regions, because each region has 4 choices. In practice it is far smaller: a good ordering (color the region with the most neighbors first) prunes most branches immediately, and the theorem guarantees the search can never run to the bottom and fail. For a map of 20 regions, 4^{20} \approx 1.1 \times 10^{12} is the paper ceiling, yet the solver usually finishes after a few hundred assignments.
Coloring a five-region map by hand
Take the default random map and suppose it produced five regions with these borders: A touches B, C, D; B touches A, C, E; C touches A, B, D, E; D touches A, C, E; E touches B, C, D. This is a common layout: a central region C ringed by A, B, D, E.
- Order by neighbor count. C has 4 neighbors, everyone else has 3. Color C first:
C = 1. - Region A neighbors C only so far. Smallest legal color is 2:
A = 2. - Region B neighbors A (2) and C (1). Smallest free color is 3:
B = 3. - Region D neighbors A (2) and C (1). Free color is 3:
D = 3. A and D never touch, so sharing color 3 is fine. - Region E neighbors B (3), C (1), D (3). Colors 1 and 3 are taken, so pick 2:
E = 2.
Final coloring: C=1, A=2, E=2, B=3, D=3. Three colors sufficed here, and no backtracking was needed. The counter reads 3. That is common: many random maps color with 3, and the fourth color only appears when a K_4 pattern (four mutually touching regions) shows up.
Reading the color counter
The counter tells you how many distinct colors your current coloring uses, not the true chromatic number of the map. Those differ. You might use all four colors on a map that a smarter ordering would color with three. The chromatic number is the minimum over all valid colorings, and finding it exactly is hard in general.
Three useful facts to read the number against:
- 2 colors possible
- Exactly when the adjacency graph is bipartite, meaning it has no cycle of odd length. A checkerboard is the classic case.
- 3 forced but 4 avoidable
- The graph has an odd cycle but no four mutually adjacent regions. Most random maps land here.
- 4 genuinely required
- The graph contains K_4, four regions each bordering the other three. Then no coloring beats 4.
If your counter shows 4 but the map has no K_4, you can repaint to 3. If it contains a K_4, four is the honest minimum and no repainting helps.
Common mistakes and misreadings
The theorem is about the flat plane (or the sphere, which behaves the same). It is not a universal law of surfaces. On a torus you can need up to 7 colors, and a Klein bottle needs up to 6. The number of colors is set by the topology of the surface, not by anything about maps in general.
A few traps show up again and again:
- Corner touches counted as borders. Two regions meeting at a single point are not neighbors. If you treat them as adjacent, you can manufacture maps that seem to need more than four colors, but they do not fit the theorem's hypothesis.
- Disconnected regions. The theorem assumes each region is one connected piece. A country in two separate parts, both needing the same color, breaks the model and can push the requirement past four. Real maps with exclaves are exactly this exception.
- Confusing "four suffice" with "four required". The theorem is an upper bound. Plenty of maps need only 2 or 3. Four is the ceiling, not the answer for every map.
- Expecting the solver to minimize colors. Backtracking finds a four-coloring fast. It does not promise the fewest possible colors. That minimum is the chromatic number, and computing it is NP-hard in general.
Related tools
The solver here is backtracking search, the same engine behind the Tower of Hanoi recursion and the Fifteen puzzle parity solver. For a graph-search puzzle solved by a different clever rule, try the Knight's tour. Euler's formula, which underlies the five-color proof, is checkable directly on the Platonic solids explorer. If you like the idea of regions defined by nearest points rather than borders, the Voronoi and Lloyd relaxation tool builds cell maps you could color the same way. And for constraint solving that ripples across a grid like a coloring problem in disguise, see Wave function collapse.
Frequently asked questions
Is the four color theorem actually proven?
Yes. Appel and Haken proved it in 1976 by reducing it to 1936 configurations that a computer verified. A 1997 proof by Robertson, Sanders, Seymour and Thomas simplified the list to 633 configurations. Both are accepted. No short proof readable entirely by hand is known.
Why does the counter sometimes show 3 when I thought I needed 4?
Because that map has no four mutually touching regions. Four is always enough, but many maps need only three. The fourth color is required only when the adjacency graph contains K_4.
Does the solver ever fail to find a coloring?
No. For any flat map the theorem guarantees a four-coloring exists, so the backtracking search always finds one and never runs out of options. It can take longer on maps with dense adjacency, but it will finish.
How many colors do I need on a globe?
Still four. A sphere and the plane are topologically the same for this purpose: puncture the sphere at any point inside a region and flatten it, and you have an equivalent flat map.
Why can seven colors be needed on a torus?
The Heawood formula gives the color bound for a surface of genus g as \lfloor (7 + \sqrt{1 + 48g}) / 2 \rfloor. For the torus, g = 1 gives 7. The plane and sphere have g = 0, which the same formula would send to 4, matching the theorem.
Related tools
3D Geometry Board
Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.
Bézier Curve Playground
Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.
Central Limit Theorem Demo
Sample from any lopsided distribution and watch the averages pile up into a bell curve.
Conway’s Game of Life
Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.
Dynamic Geometry Board
Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.
Fantasy Map Generator
Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.