The Four Color Theorem: How a Computer Solved a 100-Year-Old Math Problem

How many colors do you need to color a map so that no two neighboring countries share the same color?

Intuitively, it seems like a lot. But it turns out four is enough. And the problem itself became the first at the intersection of mathematics and what we would today call AI.

First, let’s define our terms. “Neighboring countries” means they share a border of non-zero length. If two countries touch only at a single point, they can be the same color. We also assume that countries have no enclaves — each one is a single connected region.

The Origins of the Four Color Theorem

It all started back in 1852. Francis Guthrie was coloring a map of England and noticed a pattern. Through his brother, he passed the question along to Professor Augustus De Morgan. The problem entered the world of mathematics — and resisted a solution for over 100 years.

How a Computer Finally Proved It

It wasn’t until 1976 that Appel and Haken, with the help of a computer, exhaustively checked all possible configurations of certain combinations and proved that four colors are always sufficient.

For the first time in history, a computer helped find the solution to a problem that humans had been unable to solve on their own. Mathematicians, naturally, received the result with some skepticism. The proof was re-verified and simplified over the years, but ultimately became a classic example of using computational methods — a forerunner to modern AI-assisted problem solving.

The Four Color Theorem in Graph Theory

The problem translates naturally into the language of graph theory: replace each country with a vertex and each shared border with an edge. The question then becomes: how many colors are needed to color the vertices of a planar graph so that no two connected vertices share the same color?

Why the Surface Matters

There is an important subtlety: the four color theorem applies specifically to the plane (or the sphere, which is topologically equivalent). On other surfaces, the rules change. A map drawn on a torus requires up to 7 colors, while on a Möbius strip, 6 colors are needed.

The four color theorem remains one of the most elegant results in combinatorics — simple to state, surprisingly deep, and a landmark in the history of computer-assisted mathematical proof.