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

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

がある．

　ケンペの職業は弁護士であったが，非常に優秀なアマチュア数学者でもあった．１８７９年には四色定理の不完全な証明をしたことで最も有名である．彼の証明には欠陥があったものの，全体的な考え方は非常に聡明なものであったという．

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

　３次元のｎ個の領域を塗り分けるにはｎ色必要な例を作ることができる．それに対して２次元では「どんな平面地図でも４色で塗り分けられる」ことが証明されたのだが，多くの数学者はこの証明においてコンピュータによる解析が本質的だと知ると落胆し，失望したと伝えられている．

　その証明は１９９５年にロバートソンらによって改良されてかなり簡単になったとはいえ，いまだ手計算で証明を完成させた人はいない．証明の技術的な困難さは克服されず，完全に決着したとはいいがたいのである．ともあれ，四色問題がグラフ理論の発展に対する推進力となったことは確かである．

　今回のコラムでは，前回に引き続き「四色問題」を取り上げるが，グラフ理論の先駆けともいえるオイラーの公式などについて紹介したい．

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

【１】オイラーの公式とケンペの証明

　正則とは限らない一般の多面体では

　　Σｐi＝ｐ1＋・・・＋ｐf＝２ｅ，

　　Σｑi＝ｑ1＋・・・＋ｑv＝２ｅ

となります．ｐi≧３，ｑi≧３ですから

　　２ｅ≧３ｆ，２ｅ≧３ｖ　　　（等号は三角形分割の場合）

　　ｖ−ｅ＋ｆ＝２，２ｅ≧３ｆ，２ｅ≧３ｖ

を組み合わせると，

　　２ｖ＋２ｆ＝２ｅ＋４≧３ｆ＋４　→　ｆ≦２ｖ−４

　　２ｖ＋２ｆ＝２ｅ＋４≧３ｖ＋４　→　ｖ≦２ｆ−４

　また，別の組合せ方をすると，

　　３ｖ＋３ｆ＝３ｅ＋６≦２ｅ＋３ｆ　→　３ｆ−ｅ≧６

　　３ｖ＋３ｆ＝３ｅ＋６≧２ｅ＋３ｖ　→　３ｖ−ｅ≧６

も得られます．

　さらに，オイラーの多面体定理で示される制限からいえることとして，

　　Ｆ＝ｆ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＋６（斜方切頂立方八面体）

これらの結果は極めて重要で，四色定理の証明の中核をなしています．

　ｎ本の辺をもつｆn枚の面とｎ本の辺が交わるｖn個の頂点をもつ凸多面体について，各辺は２個の頂点をもつから，Σｎｖn＝２Ｅ．また，各辺では２枚の面が交わるからΣｎｆn＝２Ｅ．したがって，

　　Σｎｆn＝Σｎｖn

が示されます．このことから，頂点の次数をｖnとし，

　　Ｖ＝ｖ3＋ｖ4＋ｖ5＋・・・

　　２Ｅ＝３ｖ3＋４ｖ4＋５ｖ5＋・・・

を

　　６Ｖ−２Ｅ≧１２

に代入すると

　　４ｖ2＋３ｖ3＋２ｖ4＋ｖ5−ｖ7−２ｖ8−３ｖ9−・・・≧１２

　　Σ（６−ｎ）ｖn≧１２　　　（等号は三角形分割の場合）

が成立します．

　　４ｖ2＋３ｖ3＋２ｖ4＋ｖ5≧ｖ7＋２ｖ8＋３ｖ9・・・＋１２≧１２

ですから，ｖ2≠０，ｖ3≠０，ｖ4≠０，ｖ5≠０のいずれかが成立します．ケンペはｖ2≠０，ｖ3≠０，ｖ4≠０のいずれか成立しても４色で十分であることを証明したのですが，ｖ5≠０の場合に間違っていたわけです．

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