四色定理

四色定理とは

四色定理とは、平面上の地図を塗り分ける際に、隣り合う領域が異なる色になるように、4色あれば必ず塗り分けられるという定理です。これは直感的には理解しやすいものの、数学的に厳密に証明するには長い年月を要しました。この定理は、グラフ理論の分野で重要な役割を果たしており、その証明はコンピュータの力を借りて初めて達成されました。

正確な定義

四色定理は、グラフ理論を用いて以下のように正確に定義されます。

平面グラフ: 平面上に描かれたグラフで、辺が交差しないものを指します。
彩色数: グラフの頂点を塗り分けるのに必要な最小の色数です。

四色定理は、「平面グラフの彩色数は4以下である」と述べています。つまり、どんな平面グラフも、4色以内で頂点を塗り分けることができるということです。

日常的な解釈の注意点

地図の塗り分けを考える際、注意すべき点があります。例えば、飛び地は所属する地域と同じ色で塗る必要があります。もし飛び地を別の色で塗ろうとすると、必要となる色数が4色以上になる可能性があります。また、現実の地図では、4つの州が一点で接する場所など、複雑なケースも存在します。これらの状況を考慮して、四色定理は「隣り合う領域が異なる色になるように塗り分ける」という条件を厳密に定義しています。

グラフ理論による表現

四色定理は、グラフ理論において「平面グラフは4彩色可能である」と表現されます。地図の領域をグラフの頂点、隣接する領域をグラフの辺と対応させることで、地図の塗り分け問題をグラフ理論の問題として扱うことができます。この表現により、四色定理の証明はグラフ理論の枠組みの中で行われました。

歴史

四色定理の歴史は1852年に遡ります。法学生のフランシス・ガスリーが、地図の塗り分けに必要な色の数について疑問を持ったことがきっかけとなり、この問題は数学者たちの間で長年未解決の難問として扱われました。

1879年には、アルフレッド・ケンプが四色定理の証明を発表しましたが、後にパーシー・ヒーウッドによってその証明に誤りが指摘されました。しかし、ケンプの証明のアイデアは、五色定理の証明につながり、地図を塗り分けるには5色で十分であることが示されました。

四色定理の完全な証明は、1976年にケネス・アッペルとヴォルフガング・ハーケンによって、コンピュータを用いて初めて達成されました。彼らは、複雑な計算をコンピュータに実行させ、約2000個の可約な配置からなる不可避集合を発見しました。この証明は、コンピュータによる複雑な計算に頼っているため、その信頼性に疑問を呈する声もありましたが、その後、複数の研究者によって改良された証明がなされ、現在では広く受け入れられています。

コンピュータによる証明

四色定理の証明は、以下の2段階に分けられます。

1. 不可避集合の発見: どんな平面グラフも、その集合に属するグラフのどれか一つを部分グラフとして含むようなグラフの集合（不可避集合）を特定します。
2. 可約性の証明: 不可避集合に属するどのグラフも、その部分グラフを除いたグラフが4色で塗り分け可能であれば、元のグラフも4色で塗り分け可能であることを証明します。

アッペルとハーケンは、コンピュータを使ってこの2つの段階をクリアし、四色定理を証明しました。彼らの証明は、当時のスーパーコンピュータを1200時間以上使用したと言われています。

証明のアイデアの概要

四色定理の証明のアイデアは、グラフの頂点を取り除き、残りのグラフを4色で塗り分けた後、取り除いた頂点を再び追加して、4色で塗り分けられることを示すというものです。この過程で、頂点の次数（その頂点に接続する辺の数）が重要な役割を果たします。特に次数が5以下の頂点が存在することが鍵となります。

証明の核心は、ケンプ鎖と呼ばれる特殊なパスの概念を利用し、色を交換することで塗り分けを可能にすることにあります。このアイデアは、五色定理の証明にも応用されました。四色定理の証明は、コンピュータによる膨大な計算を必要としたため、エレガントな証明とは言えず、「エレファントな証明」とも呼ばれました。

一般化

四色定理は、平面や球面だけでなく、ドーナツのような穴がある形状の表面にも拡張することができます。穴がg個ある表面を塗り分けるのに必要な色の数は、ヒーウッドによって公式化され、1968年に証明されました。特に、トーラス（穴が1つあるドーナツ）の場合、7色で彩色可能であることが知られています。

3彩色問題

四色定理に関連して、「与えられた地図を3色で塗り分けできるかどうか」を決定する3彩色問題という問題があります。この問題は、NP完全問題の一つであり、四色問題よりも難しいことが知られています。

四色問題とジョーク

四色定理が証明される少し前に、マーティン・ガードナーが、四色定理の反例となるような図を掲載しました。しかし、これはエイプリルフールのジョークであり、実際には四色で塗り分けることが可能でした。このジョークは大きな話題となり、多くの人が塗り分けに挑戦しました。

まとめ

四色定理は、一見単純に見える地図の塗り分け問題が、実は非常に奥深い数学的な問題であることを示しています。長年にわたる数学者たちの挑戦と、コンピュータの力を借りて初めて証明されたこの定理は、数学史における重要な出来事の一つです。また、この定理の証明は、コンピュータによる数学的な証明の可能性を示唆し、その後の数学研究にも大きな影響を与えました。

もう一度検索