The passage traces the history of the Four‑Color Theorem—the claim that any map can be colored with at most four colors so that adjacent regions differ. It began in 1852 when Francis Guthrie posed the problem to Augustus de Morgan, and early attempts (including Alfred Kemp’s 1879 proof) failed. By converting maps to planar graphs, researchers sought an unavoidable set of reducible configurations; Kemp’s approach showed that a minimal counter‑example could not exist, but Percy Haywood later found a flaw in his recoloring method, leaving the theorem unproved for decades. In the 1960s–70s, growing computer power enabled Wolfgang Haken and Kenneth Appel to examine a large unavoidable set of 1,936 reducible configurations, completing the first major computer‑assisted proof in 1976 after over a thousand hours of computation. This proof sparked debate about what constitutes a legitimate mathematical proof, but over time computer‑assisted methods became accepted. The Four‑Color Theorem’s resolution not only settled a long‑standing puzzle but also accelerated graph theory and demonstrated the fruitful partnership between mathematics and computing.
1. Sudoku puzzles, wedding seating plans, and radio frequency assignments are all instances of the map‑coloring problem.
2. The map‑coloring problem asks how many colors are needed to color any map so that adjacent regions have different colors.
3. The Four Color Theorem states that four colors are sufficient to color any map.
4. In 1852, Augustus de Morgan introduced the map‑coloring problem in a letter to Sir William Rowan Hamilton.
5. Francis Guthrie, de Morgan’s former student, first posed the question after observing that UK counties could be colored with four colors.
6. Early attempts to prove the Four Color Theorem failed.
7. In 1879, Alfred Kempe published a proof that was later shown to be incorrect.
8. Kempe’s approach used the concepts of unavoidable sets and reducible configurations, converting maps to planar graphs.
9. In 1890, Percy Heawood discovered an error in Kempe’s proof, showing it only worked for vertices with up to four neighbors.
10. After Heawood’s discovery, the theorem remained a conjecture for about fifty years.
11. By the late 1960s and early 1970s, computers had become fast enough to assist in complex mathematical proofs.
12. In 1976, Wolfgang Haken and Kenneth Appel at the University of Illinois proved the Four Color Theorem using computer assistance.
13. Their proof identified an unavoidable set of 1,936 reducible configurations that every map must contain.
14. The computer‑assisted proof required more than a thousand hours of computer time.
15. The proof sparked debate about what constitutes a legitimate mathematical proof and the role of computers in mathematics.
16. Over time, the use of computers in theoretical mathematics gained broader acceptance.
17. Today, mathematicians routinely use computers to verify or generate proofs.
18. The Four Color Theorem stimulated major advances in graph theory and network theory.
19. Graph and network models derived from this work are now used to study disease spread and computer network connectivity.