What is the four color conjecture and why does it matter?
Imagine you are coloring a political map and want to ensure that no two neighboring countries share the same color. How many colors do you need? This deceptively simple question launched one of the most famous problems in all of mathematics -- the four color conjecture -- and its resolution would eventually require an entirely new kind of proof.
The four color theorem states that any map drawn on a plane (or sphere) can be colored with at most four colors so that no two adjacent regions -- regions sharing a common border segment, not merely a single point -- receive the same color. Though easy to state and simple to verify for small maps, proving it for every possible map turned out to be extraordinarily difficult.
Try your hand at coloring a map using only four colors. Select a color from the palette and click regions to fill them in. The system will highlight conflicts -- pairs of adjacent regions that share the same color. Can you color the entire map with zero conflicts?
Click a color above, then click regions on the map. Adjacent regions sharing a border will show a conflict (pulsing red border) if they have the same color.
Key insight: Adjacent regions sharing a border (not just a point) must get different colors. Four colors always suffice for any map, no matter how complex.
Not every map requires all four colors. Some maps can be colored with just two or three. The minimum number of colors needed is called the chromatic number. Explore these examples to see maps that require exactly 2, 3, and 4 colors -- and try to see why fewer colors are not enough.
Chromatic number: 2
A bipartite arrangement of 4 regions. Like a checkerboard, you can alternate two colors and never have neighbors clash.
Try to color each example using exactly its chromatic number of colors. Toggle between map and graph views to see the dual representation.
Key insight: Some maps genuinely require 4 colors -- you can always find configurations where three colors are not enough. The four color theorem says four always suffice.
The four color problem has a remarkable history stretching over 150 years. From its origins as a casual observation about map coloring to its controversial computer-assisted proof and eventual formal verification, this timeline traces the key moments in one of mathematics' most celebrated stories.
While coloring a map of the counties of England, Francis Guthrie noticed that four colors sufficed and asked whether this was always the case. His brother Frederick passed the question to Augustus De Morgan, who popularized it among mathematicians.
Click any dot on the timeline to learn about that milestone in the history of the four color theorem.
Key insight: The four color theorem took 124 years from conjecture to proof and was the first major theorem proved with significant computer assistance.