Wikipedia Deep Dive

Four color theorem

7 min read

In 1852, a young man named Francis Guthrie was trying to color a map of England's counties. He noticed something peculiar: no matter how he arranged the boundaries, only four colors were ever needed—and this seemingly simple observation would baffle mathematicians for over a century.

The Four Color Theorem states that any map, however complex, can be colored using at most four colors so that no two adjacent regions share the same color. "Adjacent" here means sharing an actual boundary segment—not merely touching at a corner point. It's the kind of problem that sounds like a puzzle you might pose after too much wine at dinner, but it became one of mathematics most celebrated results.

The Origin of a Problem

The story begins with Francis Guthrie, a student who was attempting to color the map of England's counties around 1852. While working on this seemingly trivial task, he realized that only four colors were sufficient to color all the regions without any two adjacent ones sharing a color.

Guthrie mentioned this observation to his brother Frederick, who was studying under Augustus De Morgan at University College London. Frederick took the question to De Morgan, and thus began one of mathematics most famous conjectures.

De Morgan later described the problem in his own words: "A student of mine asked me to give him a reason for a fact which I did not know was a fact—and do not yet. He says that if a figure be any how divided and the compartments differently colored so that figures with any portion of common boundary line are differently colored—four colors may be wanted but not more."

The problem was formally posed in The Athenaeum in 1854 under the initials "F.G." (presumably Francis Guthrie), and De Morgan reintroduced it in 1860. The theorem became known as the Four Color Problem—and later, the Four Color Theorem.

Early Attempts at Proof

The conjecture fascinated mathematicians for decades. Several prominent proofs were proposed, but each one turned out to be flawed.

In 1879, Alfred Kempe presented a proof that was widely acclaimed and accepted without scrutiny. It stood unchallenged for eleven years until Percy Heawood exposed the flaw in 1890—but not before Heawood used similar reasoning to prove the Five Color Theorem, showing that five colors always suffice.

Peter Guthrie Tait proposed another proof in 1880, which remained accepted until Julius Petersen demonstrated its error in 1891. Each false proof held for eleven years before being debunked—a testament to how subtly wrong these arguments could be.

Interestingly, Tait had shown that the Four Color Theorem was equivalent to a statement about a particular type of graph—what we now call an "snark"—being non-planar. This connection would later become central to the theorem's solution.

The Journey Toward Proof

During the 1960s and 1970s, German mathematician Heinrich Heesch developed revolutionary methods using computers to search for a proof. He was the first to employ discharging—a technique that proved crucial in the eventual Appel–Haken proof. He also expanded on the concept of reducibility and, with Ken Durre, developed a computer test for it.

The theorem was finally proven in 1976 by Kenneth Appel and Wolfgang Haken—a landmark achievement because it was the first major theorem to be proved using a computer. Their proof required analyzing an enormous number of "reducible configurations," essentially examples of maps with particular properties that needed checking.

This approach used what mathematicians call the "method of exhaustion": they showed that any counterexample to the theorem must contain certain patterns, and then demonstrated that no such pattern could exist by systematically checking all possible cases through computer verification.

The Controversy of Computer Proofs

When Appel and Haken announced their proof, it sparked intense controversy. The proof was infeasible for a human to check by hand—it required massive computational power. Some mathematicians welcomed the result as a breakthrough, while others remained skeptical. The concern was understandable: how could anyone accept a proof they couldn't verify themselves?

The original Appel–Haken proof used an estimated 1,000,000 logical decisions in its computer portion—numbers that would have been unthinkable in earlier mathematical eras.

This criticism has faded over time, and the proof gained wide acceptance. But reservations remained, leading mathematicians to seek independent verification.

Modern Verifications

In 1993-1997, Robertson, Sanders, Seymour, and Thomas improved upon the original proof by reducing the number of configurations to 633—still an extremely long case analysis but more manageable than before.

Then in 2005, Georges Gonthier verified the theorem using general-purpose theorem-proving software, providing a different kind of validation that gave many mathematicians renewed confidence in the result.

The Graph Theory Formulation

The coloring of maps can be stated more abstractly in terms of graph theory. A map's regions become vertices in a graph, and adjacent regions become edges connecting those vertices. In this formulation, the Four Color Theorem becomes: every planar graph is four-colorable—meaning its vertices can be colored with at most four colors so no two connected vertices share the same color.

This abstraction reveals why the problem matters beyond mapmaking: it touches on fundamental questions about how we understand spatial relationships and coloring constraints in mathematics.

Important Caveats

Two crucial clarifications make this theorem meaningful:

First, regions are only considered adjacent if they share a boundary segment of non-zero length. Two regions that merely touch at a single point—or where three or more regions meet—are not adjacent. Without this rule, a pie-chart-shaped map could have arbitrarily many regions all "adjacent" at a common corner and require infinitely many colors.

Second, bizarre regions with finite area but infinitely long perimeters are excluded from consideration—maps containing such regions might require more than four colors.

There's also the matter of countries not being contiguous. In real-world geopolitics, countries sometimes have exclaves: Angola surrounds Cabinda Province; Azerbaijan encompasses its Nakhchivan Autonomous Republic; Russia holds Kaliningrad Oblast; France has overseas territories; the United States includes Alaska as separate land. If we require entire territories to share colors, four colors are sometimes insufficient.

In one simplified map scenario, two regions labeled "A" belonging to the same country required five colors because together they were adjacent to four other regions—each of which was adjacent to every other region.

The Five Color Theorem

Interestingly, a weaker version—the Five Color Theorem—was already proven in the 1800s using simpler arguments. This states that any map can be colored with at most five colors. From this, we infer the stronger Four Color Theorem's statement must hold—but actually proving it required much more sophisticated reasoning.

The difference is significant: demonstrating five colors requires relatively straightforward mathematical arguments, while four colors demanded far deeper analysis and eventually computers.

Legacy

The Four Color Theorem stands as a landmark in mathematics not merely for its conclusion but for what it represents. It was the first major theorem proven through computational means, opening doors to verifications that seemed impossible in earlier eras.

Today, the theorem remains fundamental in graph theory and cartography. Its resolution ended more than a century of mathematical inquiry, proving that even puzzles that seem simple can carry profound complexity underneath.

Francis Guthrie, who started coloring England's counties in 1852, could never have imagined where his observation would lead—but the four colors he noticed became one of mathematics most compelling stories: a problem so simple to state it could be explained to any curious child, yet so difficult to prove it required computers and decades of effort from some of history's brightest minds.