Exercise 2140Combinatorics › Graph theoryM1Added 3 Nov 2026
The four-color theorem proof (history)
#four-color#history#proof
Statement
State the history of the four-color theorem.
Hint
Conjectured 1852, proved 1976 by Appel and Haken using computer assistance.
Show solutionHide solution
Solution
Conjecture. Guthrie (1852) conjectured every planar map can be colored with 4 colors.
Attempts. Kempe (1879) gave a flawed proof; Heawood (1890) found a gap but proved 5 colors suffice.
Proof. Appel and Haken (1976) proved it using a computer to check 1936 reducible configurations.
Simplification. Robertson, Sanders, Seymour, Thomas (1996) gave a simpler proof with 633 configurations.
Conclusion. The four-color theorem is a landmark result, notable for its reliance on computer verification.