■2色定理の証明(その5)

 コンピュータ計算による網羅的な探求の例としては,以下の2つの有名な極値問題が解決されたことがあげられる.

(1)1988年,ヘールズはケプラーの球の詰め込み問題(1611年)が正しいことを示した.

(2)1976年,ハーケンとアッペルは4色問題(1852年)が正しいことを示した.

 4色問題(平面上の地図を塗り分けるには4色が必要かつ十分である)は素人でも理解できる問題である.見た目には簡単には思えるが,実は容易に解ける問題ではなく,多くの間違った証明を生み出し,失敗と部分的解決が繰り返されてきた悪名高い問題であるが,かくして4色問題は4色定理となった.

 今回のコラムでは,地図が2色で塗り分けられるための必要十分条件を見いだす問題=2色定理を取り上げることにする.2色問題は地図塗り分け問題の特別な場合にあたるのである.

===================================

【1】2色問題

 紙の上に鉛筆で閉曲線を描く.その際,自分自身と交差すること,また,交点では2個以上の弧が交わってもよいことにする.次に,閉曲線から得られた地図に色を塗るのだが,ある国を黒く塗りつぶし,国境線で隣り合う国はそのままにしておく.

 その結果は市松模様となるが,これは偶然ではない.この事実を初めて知ったのは高校生のときであるが驚き,そして不思議に思ったものである.

 しかし,2色定理の証明はあっけないほど簡単である.どの隣接する2面も同じ色でないように,白と黒の市松模様に塗ることができるためには,1の頂点で偶数の面が交わらなければならない(=頂点の次数はすべて4以上の偶数)ことに気づきさえすればよい.

===================================