Map Coloring History

Graph Theory · Axiom Academy

From a simple puzzle to one of mathematics' greatest challenges. Try coloring this map so that no neighboring regions share the same color. How many colors do you need? The Four Color Conjecture (1852) In 1852, Francis Guthrie noticed something remarkable while coloring a map of England. While coloring a map of English counties, student Francis Guthrie noticed he only needed four colors. He wondered: Is this true for ALL maps? Alfred Kempe published a "proof" that was accepted for 11 years before Percy Heawood found a critical error. Mathematicians tried countless approaches. The problem seemed simple but resisted every attempt at proof. It became one of mathematics' most famous unsolved problems. Kenneth Appel and Wolfgang Haken used 1,200 hours of computer time to check 1,936 special cases. The first major theorem proved with computer assistance! The breakthrough came from transforming the problem. Click "Transform to Graph" to see the magic! What Makes Planar Graphs Special? Not all graphs need only 4 colors. Planar graphs have unique properties. How many colors are needed to color any map so neighbors differ? Maps → Planar Graphs: Regions become vertices, borders become edges Planar graphs have special structure (Euler's formula: V - E + F = 2) that limits their complexity Four colors are always sufficient for any planar graph!

This is the written version of the interactive lesson above. See the full Graph Theory course.