📂グラフ理論

四色地図問題

ビルドアップ

四色地図問題とは、隣接する領域が互いに区別できるように地図を色塗りするには4つの色が十分かという問題だ。地図が複雑になれば色も増えるはずだが、隣接する部分だけが異なればいいので、思ったより多くの色は必要ない。例えば、次は世界地図を$4$色だけで塗ったものだ。

歴史的に、1852年にイギリスの植物学者フランシス・グースリー^{francis Guthrie}が英国の地図を色で区別し塗る際、たった4つの色だけを使用して各州を区分できることを発見し、デ・モルガンの定理で有名な師匠デ・モルガンに数学的に証明できるか尋ねた。四色問題が学問的に真剣に言及されたのは、1879年のアーサー・ケイリーの論文が初めてだったとされる。四色問題は数学的に次のように述べられる。

任意の地図は$4$-塗り分け可能か？

数学、特にグラフ理論では、地図は$3$-連結平面グラフとして定義される。

その後、1879年にアルフレッド・ケンペ^{alfred Kempe}と1880年にピーター・テイト^{peter Tait}は四色定理を証明したと主張したが、それぞれ11年後にパーシー・ヒーウッド^{percy Heawood}とジュリウス・ピーターセン^{julius Petersen}によって証明の誤りが発見された。ヒーウッドは代わりに$5$色で地図を塗り分けできるという五色定理を証明した。

四色問題は一見シンプルに見えるが、この「任意の地図」という条件が思ったよりも簡単ではなかった。五色定理からただ一つの色を減らすだけで、証明を困難にしていた膨大なケースの数が発生する。そこで、1976年にアッペル^appelとハーケン^hakenは地図の形を単純化して有限のケース数に減らし、それら全てのケースをコンピュータで検討する方法で四色問題を解決した。

アッペル・ハーケン四色定理 ¹

任意の地図は$4$-塗り分け可能だ。

意義

コンピュータを使用した証明は当時大きな論争を引き起こし、それ以降も多くの批判を受けた。純粋数学の美しさに魅了された人々にとって、1936のケースを一つ一つ確認することはあまり「数学的」ではないと見えるかもしれず、それが本当に証明と呼べるものか疑問を呈する人もいた。しかし、いずれにせよアッペルとハーケンの証明は問題が提示されてからちょうど100年後に解決された最初の解答として認められている。