【２】四色定理

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

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

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

　四色問題の証明では，地図を電気回路とみなして

　　４ｆ2＋３ｆ3＋２ｆ4＋ｆ5−ｆ7−２ｆ8−３ｆ9−・・・＝１２

の条件の下の放電（電荷の移動）に帰着させる（放電法）のであるが，この手続きは場合分けの数が膨大で，約１８００通りもの場合をチェックしなければならず，コンピュータによる解析に依存せざるを得なかったのである．

　アペルとハーケンの後も放電法の改良が続けられ，１９９４年，ロバートソン，サンダース，シーモア，トーマスの４人が新たな１章をつけ加えた．しかし，これとて基本的にはアペル，ハーケンと同じコンピュータ路線であり，場合分けが約６００通りに軽減されているものの，四色問題の証明にはどうしてもコンピュータが必要であった．

　四色定理の証明はロバートソンらによって改良されてかなり簡単になったとはいえ，いまだ手計算で証明を完成させた人はいない．その後、ワーナーとゴンティエによって、人間の頭でも終える形で証明されたらしい。コンピュータを使わない証明にはこれまでにないようなまったく新しいアイディアが必要になると思われるが，そうしたアイディアは今日もなお登場していないのである．

　ともあれ，四色問題がグラフ理論の発展に対する推進力となったことは確かである．

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