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

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