五色定理――可約配置の不可避集合をつくる

　四色定理が正しいのだから，それを弱めた主張「平面上のいかなる地図もたかだか五色で塗り分けられる」も，当然成り立つ。この五色定理の証明は比較的簡単だ。「可約配置」の「不可避集合」を作って証明するのは四色定理と同様である。
　まず，準備としてある有名な公式が必要になる。グラフ理論の基礎「オイラーの多面体定理」である。これは，多面体の面，辺，頂点の数（それぞれＦ，Ｅ，Ｖ）の間の関係を示す公式であり，「Ｖ＋Ｆ−Ｅ＝２」という簡単だがものすごく重要な式である。平面の地図でも，全部の国の外側領域もまた一つの国だと考えて，国，国境線，国境線の交点の数（それぞれＦ，Ｅ，Ｖ）の間に全く同じ式が成り立つ。地図の外側は国でないと考えれば，「Ｖ＋Ｆ−Ｅ＝１」だ。「Ｖ＋Ｆ−Ｅ」が不変量になるというのがキモであり，一般に，種数ｎのトーラス上の地図や，ドーナツやプレッツェルのようにｎ個の穴があいた多面体では「Ｖ＋Ｆ−Ｅ＝２−２ｎ」が成り立つ。
　面，辺，頂点の数がオイラーの公式を満たさないような多面体は存在しない。例えば，面がすべて正五角形の多面体は，正十二面体しかありえない。Ｆ面体の面がすべて正五角形とすると，辺はＥ＝５Ｆ／２本（二つの面が一つの辺を共有することに注意），頂点はＶ＝５Ｆ／３個である（各面の頂は鈍角だから，四つ以上の面は一つの頂点を共有できない）。すると公式から，２＝Ｖ＋Ｆ−Ｅ＝Ｆ／６。よってＦ＝１２。このようにして正多面体は五種類しかないことが分かり，おのおのの面，辺，頂点の数も分かる。これと同様に，平面上の地図における国々の配置にも制限がある。
　地図の塗り分け問題を考えるときには，すべての国境線が一つながりになっていて，かつ四本以上の国境線が一点で交わらない地図を考えれば十分である。このような地図では，国境線は必ず三本で交わるから三枝地図という（二本の国境線は「交わる」ことができないことに注意，そのように見えるのは単なる一本の国境線だ）。なぜ三枝地図を考えれば十分なのかというと，三枝地図は他の地図よりも塗り分けの難しい地図だからだ。国境線が四本以上交わる点をもつ地図Ａと，その地図のその交点近傍に新たな国を設けた地図Ａ’（これは三枝地図）を考えてみよう。Ａ’の新興国は，Ａで一点を共有していた四以上の国に取り囲まれており，これらの国々すべてと異なる色で塗らなければならない。だから，Ａがｎ色で塗り分けられたとしても，Ａ’がｎ色で塗り分けられる保証はない。Ａのｎ色塗り分けを，そのままＡ’に拡張しようとするとｎ＋１色塗り分けになってしまう。逆に，三枝地図Ａ’があるパターンで塗り分けられたとすると，もとの地図Ａは何の工夫をしなくてもＡ’の新興国を消滅させることで必ず塗り分けられ，この操作で色数は変わらないか一つ減る。三枝地図は最も塗り分け難い地図なのだ。
　三枝地図のもつ顕著な特徴として，「いかなる地図にも五本以下の国境線をもつ国が存在する」という定理がある。国境線をｎ本もつ国を「ｎ辺国」と呼ぼう。ｎ辺国は，周囲をたかだかｎカ国に囲まれている。なお一辺国は三枝地図に存在しない。国の配置の集合｛二辺国，三辺国，四辺国，五辺国｝を考える。すると先の五辺以下国存在定理は，この集合が「不可避集合」であることと等しい。だから，もし二〜五辺国がすべて可約配置であれば，ｎ色定理は証明される。そして，五色以上の塗り分けに関しては，二〜五辺国はいずれも可約配置になる。
　その前に五辺以下国存在定理を証明しておこう。これは，例のオイラーの公式から導かれる。平面地図の国数をＦ個，国境をＥ本，国境の交点をＶ個とすると，Ｖ＋Ｆ−Ｅ＝１である。ｎ辺国の数をＦnで表すと，Ｆ＝ΣＦn，Ｅ＝ΣｎＦn／２，三枝地図を考えるから，Ｖ＝ΣｎＦn／３である。これを代入すると，１＝Ｖ＋Ｆ−Ｅ＝Σ（６−ｎ）Ｆn／６という式が得られる。右辺のΣの中身はｎ＝６については０，ｎ≧７については負である。だから五辺以下の国が存在しないような地図では，右辺の和が正になれず，１であることと矛盾する。つまりそんな地図はないから，｛二辺国，三辺国，四辺国，五辺国｝は不可避集合である。
　さて，可約配置である。五色問題で言えば，可約配置とは次のようなものだ。「ある地図（Ｇ）からある配置の国（Ｐ）を除いた地図（Ｇ−Ｐ）」が五色塗り分け可能であると仮定する。このとき，Ｇ−Ｐの五色塗り分けをもとにして，もとの地図Ｇの五色塗り分けが得られる場合がある。得られるか，得られると限らないかはＰがどんな配置かに依存する。Ｇ−Ｐのどんな五色塗り分けについても，それからＧの五色塗り分けが常に得られるような配置Ｐを可約配置というのだ。可約配置は，最小反例には絶対に含まれない。なぜかは背理法でわかる。もし最小反例Ｈが可約配置Ｐを含むとすると，Ｈ−Ｐは最小反例より国が少ない地図だから反例ではあり得ない。しかし，Ｈ−Ｐが五色で塗り分けられるなら，Ｐの可約性によりＨも五色で塗り分けられ，矛盾する。
　もし，可約配置の不可避集合が存在するなら，つまり，どんな地図でも必ず可約配置を含むなら，最小反例Ｈも可約配置を含まざるを得ない。しかし最小反例は決して可約配置を含まないのだから，矛盾が生じる。すなわち「最小反例がある」という前提が間違っていたのであり，五色定理が証明される。さあ，残るは可約性を検証するだけだ。
　五色問題において，二辺国，三辺国，四辺国がいずれも可約配置であるのは，自明である。なぜなら，二〜四辺国の周りには，たかだか四つの国しかなく，それらの国に使われる色はたかだか四色である。使える色は五色あるから，その二〜四辺国を周囲と別の色で塗れるのはあたりまえだ。問題は五辺国である。五辺国を取り巻く五国が，五色を使い尽くしてしまっている場合がある。実はこのような場合でも，五辺国の外側の国々の塗り分けを適切に修正することで，五辺国を含めて五色で足りるように塗り分け直せるのだ。それを示すには，ケンペ鎖という概念を用いる。四色問題の誤った証明を出したケンペの考えた手法である。
　五辺国の周囲五国の色を，時計回りに０，１，２，３，４と符号をつけて区別する。これら五国を順に国０，国１，国２，国３，国４と呼ぼう。そして国０と国２に注目する。ここで，五辺国の周囲にある五国の，さらに外側にある国々の塗り分け状態に応じて，二つの場合に分ける。
　場合?。国０から出発して，０−２−０−２−…という二色の交互のつながり（ケンペ鎖）が，国２にまで届いていない場合。この場合には，国０から始まる先のケンペ鎖において，０と２の色を入れ替えても国２の色に影響しない。そうすると，五辺国の周囲に色０がなくなるから，五辺国に色０を塗ることができる。六色目は必要ない。
　場合?。場合?以外の場合。この場合，国０から国２まで，０と２のケンペ鎖がつながっている。ここで今度は国１と国３に注目する。すると，国１から出発するケンペ鎖は，国３までつながっていない。なぜなら，先の０−２ケンペ鎖によって必ず分断されているからである。よってこの国１から出発する１−３ケンペ鎖において，１と３の色を入れ替えても国３の色は変わらない。そうすると，五辺国の周囲に色１がなくなるから，五辺国に色１を塗ることができる！六色目は要らない！
　結局，五辺国の周囲の五国が五色で塗られていても，地図全体を適切に塗り直せば，五辺国を含めた地図を必ず五色で塗り分けることができる。つまり五辺国も可約である。以上によって，五色定理が証明された。