２０世紀のうちに解決された悪名高き難問に，四色問題

　　「任意の平面地図は高々４色で色分けできるか？」

がある．５色で色分けできることはヒーウッドによって１００年以上も前から知られていたが，四色問題が肯定的に解決されたのは１９７０年代後半のことで，アペルとハーケンはコンピュータを使ってこの証明を成し遂げた．四色問題の証明は場合分けの数が膨大で，コンピュータによる解析に依存せざるを得なかったのである．

　３次元のｎ個の領域を塗り分けるにはｎ色必要な例を作ることができる．それに対して２次元では「どんな平面地図でも４色で塗り分けられる」ことが証明されたのだが，多くの数学者はこの証明においてコンピュータによる解析が本質的だと知ると落胆し，失望したと伝えられている．

　その証明は１９９５年にロバートソンらによって改良されてかなり簡単になったとはいえ，いまだ手計算で証明を完成させた人はいない．ともあれ，四色問題がグラフ理論の発展に対する推進力となったことは確かである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝