四色定理
1852年に法科学生のフランシス・ガスリーが数学専攻である弟のフレデリック・ガスリー(英語版)に質問したのを発端に問題として定式化され、19世紀後半になって数学者がその話を聞いて証明を試みたが、多くの数学者の挑戦をはねのけ続けていた。
1879年、アルフレッド・ケンプ(英語版)による証明が『アメリカ数学ジャーナル』誌上で発表された。この証明は妥当と見なされていたが、1890年になってパーシー・ヒーウッド(英語版)により不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。これは五色定理と呼ばれている。4色で十分かどうかは、グラフ理論における最も有名な未解決問題として残った。
1976年にケネス・アッペル(英語版)とヴォルフガング・ハーケンは、ハインリヒ・ヘーシュ(英語版)により考案された「放電法」と呼ばれる手続きを改良し、コンピュータを利用して約2000個の(後に1400個あまりに整理された)可約な配置からなる不可避集合を見出し、四色定理を「証明」するに至った。