■四色問題（その９）
２０世紀のうちに解決された悪名高き難問に，四色問題
「任意の平面地図は高々４色で色分けできるか？」
がある．５色で色分けできることはヒーウッドによって１００年以上も前から知られていたが，四色問題が肯定的に解決されたのは１９７０年代後半のことで，アペルとハーケンはコンピュータを使ってこの証明を成し遂げた．四色問題の証明は場合分けの数が膨大で，コンピュータによる解析に依存せざるを得なかったのである．
３次元のｎ個の領域を塗り分けるにはｎ色必要な例を作ることができる．それに対して２次元では「どんな平面地図でも４色で塗り分けられる」ことが証明されたのだが，多くの数学者はこの証明においてコンピュータによる解析が本質的だと知ると落胆し，失望したと伝えられている．
その証明は１９９５年にロバートソンらによって改良されてかなり簡単になったとはいえ，いまだ手計算で証明を完成させた人はいない．ともあれ，四色問題がグラフ理論の発展に対する推進力となったことは確かである．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】オイラーの多面体定理
オイラーの多面体定理で示される制限からいえることとして，
Ｆ＝ｆ3＋ｆ4＋ｆ5＋・・・
２Ｅ＝３ｆ3＋４ｆ4＋５ｆ5＋・・・
を
６Ｆ−２Ｅ≧１２
に代入すると
３ｆ3＋２ｆ4＋ｆ5−ｆ7−２ｆ8−３ｆ9−・・・≧１２
地図のように２つの辺に囲まれた領域まで許すことにすると，この数え上げ公式は
４ｆ2＋３ｆ3＋２ｆ4＋ｆ5−ｆ7−２ｆ8−３ｆ9−・・・＝１２
となります．いずれにせよ，係数が１ずつ小さくなり，それが０となるｆ6は式中に現れません．
このことから，ｆ3，ｆ4，ｆ5の少なくとも１つは０でない→多面体には３角形か４角形面か５角形面が少なくとも１つなければならない，同様に，多面体の少なくとも１つの頂点は３次か４次か５次でなければならない→すべての頂点の次数が６以上となることは不可能であり，必ず次数が５以下の頂点をもつことが導き出されます．これもオイラーが知っていた結果であるということです．
ここで，
(1)ｆ2＝ｆ3＝ｆ4＝０だとすると，少なくとも１２個のｆ5がなければならないことになる
(2)多面体の面がすべてｆ5とｆ6であるならば，ｆ5＝１２（切頂二十面体）
(3)多面体の面がすべてｆ4とｆ6であるならば，ｆ4＝６（切頂八面体）
(4)多面体の面がすべてｆ4，ｆ6，ｆ8であるならば，ｆ4＝ｆ8＋６（斜方切頂立方八面体）
これらの結果は極めて重要で，四色定理の証明の中核をなしています．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】ヒーウッドの公式
オイラーの公式は単純ですが，要はその使い方というわけで，たとえば，多面体には３角形か４角形面か５角形面が少なくとも１つなければならないことはもっと簡単に証明できます．
どの領域も少なくとも６つの領域で囲まれていると仮定すると
６ｆ≦２ｅ
また，このような問題を解くにあたっては，すべての交点で３本の境界線が会している地図だけを考えればよいので，
３ｖ≦２ｅ
これらをオイラーの公式に代入すると
ｖ−ｅ＋ｆ≦１／３ｅ−ｅ＋２／３ｅ＝０≠２
となって矛盾を生じます．したがって，５個以下の隣接領域しかもたない領域が少なくともひとつあることになります．
平面や球面上に描かれた地図に関するオイラーの公式は
ｖ−ｅ＋ｆ＝２
でしたが，トーラス上の地図に関するオイラーの公式は
ｖ−ｅ＋ｆ＝０
です．
トーラスでは６個以下の隣接領域しかもたない領域が少なくともひとつあることを証明するために，どの領域も少なくとも７つの領域で囲まれていると仮定すると
７ｆ≦２ｅ
また，３ｖ≦２ｅですから
ｖ−ｅ＋ｆ≦２／７ｅ−ｅ＋２／３ｅ＝−１／２１ｅ≠０
という矛盾を引き出すことができます．
したがって，トーラスでは６個以下の隣接領域しかもたない領域が少なくともひとつあることになります．このことを利用すると，
「トーラス上のどんな地図でも７色で塗り分けられる」
ことが証明されます．ヒーウッドは実際に７色を必要とする例もあげています．
これを証明したヒーウッドはさらにｇ個の穴があいたトーラス上の地図に関するオイラーの公式
ｖ−ｅ＋ｆ＝２−２ｇ
を利用して
(1)２個の穴があいているトーラス上の地図はどれも８色で塗り分けられる
(2)３個の穴があいているトーラス上の地図はどれも９色で塗り分けられる
・・・・・・・・・・・・・・・・・・・・・・・・
(3)１０個の穴があいているトーラス上の地図はどれも１４色で塗り分けられる
に引き続いて，
(4)ｇ個の穴があいているトーラス上の地図はどれもＨ（ｇ）色で塗り分けられる
Ｈ（ｇ）＝［｛７＋√（１＋４８ｇ）｝／２］
を証明しました．
［・］はガウス記号で，
ｇ：１，２，３， ４， ５， ６， ７， ８， ９，１０
Ｈ：７，８，９，１０，１１，１２，１２，１３，１３，１４
となるのですが，しかし，ヒーウッドはｇ≧２に対してそのような地図が実在することを示すことはできませんでした．そのため，この問題は「ヒーウッド予想」と呼ばれることになりました．
１９６８年，リンゲルとヤングスは，ｇ個の穴のあいているトーラス上にこれだけの色を必要とする地図が存在することを証明したのですが，ヒーウッド予想（１８９０年）が最終的に証明されるまでには７７年もの歳月が必要だったというわけです．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
