五色定理

グラフ理論における五色定理（ごしょくていり、英: five color theorem）とは、領域に分けられた平面、例えばある州を郡に分けた政治地図が与えられたとき、5種類以下の色を使って、隣接する領域が必ず別の色になっているように各領域を塗り分けられるという定理である。

五色定理はそれより強い四色定理の系であるが、証明ははるかに易しく、1879年にアルフレッド・ケンプ（英語版）（ケンペとも）が四色定理（予想）を証明し損ねたときの論法に基づき行える。パーシー・ジョン・ヒーウッド（英語版）は11年後にケンプの誤りを発見し、それを元に五色定理を証明した。

証明のアウトライン

まず、与えられた地図に単純な平面グラフ $G$ を対応させる。つまり、地図の各領域をグラフの頂点とし、2領域が隣接しているときかつそのときに限り、対応する2頂点を1つの辺で結ぶものとする。こうして問題はグラフの彩色問題に変換される：各頂点に色を塗って、どの辺についても端点である2頂点の色が一致しないようにできるか。

グラフ $G$ は単純平面グラフである、つまり平面上にどの2辺も交差させることなく描くことができ、かつどの2頂点間にも2本以上の辺が存在せず、ループも存在しないので、平面のオイラー標数を用いることで、グラフ $G$ には最大でも5本の辺によってしか接続されていないような頂点が存在することが証明できる（注意：五色定理の仮定（色の数が最大で5）が使われるのはこの箇所だけである。もし同じ手法で四色定理を証明しようとしても、この段階で頓挫する。実際、正二十面体グラフ（icosahedral graph）は5-正則な平面グラフであり、接続する辺が4本以下であるような頂点は存在しない）。このような頂点を1つ選んで $v$ と呼ぶことにする。

今、頂点 $v$ を $G$ から取り除く。このようにして得られるグラフ $G'$ は頂点の数がグラフ $G$ よりも1個だけ少ないので、数学的帰納法により5色で彩色できるとしてよい。頂点 $v$ は他の5個の頂点と隣接しているとする（4個以下であれば、隣接する頂点に使われていない色を塗ることでグラフ $G$ の彩色は終わる）。そこでこれらの $v$ と隣接していた5頂点を（反）時計回りに $v_{1}$ , $v_{2}$ , $v_{3}$ , $v_{4}$ , $v_{5}$ とする（番号の振り方は $G$ の描き方に依る）。もしこれらが5つの異なる色で塗られていなければ、明らかに頂点 $v$ を使われていない色で塗ることでグラフの彩色が終わる。

そこで、頂点 $v_{1}$ , $v_{2}$ , $v_{3}$ , $v_{4}$ , $v_{5}$ はそれぞれ色 1, 2, 3, 4, 5 で塗られていると仮定する。

グラフ $G'$ から、色1または3で塗られた頂点と、それらを接続する辺だけを取り出した部分グラフ $G_{1,3}$ を考える。明らかにどの辺も色1の頂点と色3の頂点を結ぶ（これをケンプ鎖（英語版）という）。もし $v_{1}$ と $v_{3}$ とがグラフ $G_{1,3}$ の異なる連結成分に属するならば、 $v_{1}$ が属す連結成分で色1と色3を交換することで、頂点 $v$ を色1で塗ることができるようになり、証明が終わる。

そうでない場合、 $v_{1}$ と $v_{3}$ とはグラフの同一の連結成分に属すことになるので、色1と色3の頂点のみを伝ってこれらを結ぶ $G_{1,3}$ の道を見つけることができる。

ここで今度は、グラフ $G'$ から色2または4で塗られた頂点とそれらを接続する辺だけを取り出した部分グラフ $G_{2,4}$ に目を向け、同じ議論を繰り返すことにする。すると、グラフ $G_{2,4}$ の $v_{2}$ を含む連結成分において色2と色4を交換することで頂点 $v$ が色2で塗れるようになるか、色2と色4の頂点のみを伝って $v_{2}$ と $v_{4}$ を結ぶ $G_{2,4}$ の道を見つけることができるかの、二つに一つである。ところが後者はあり得ない。なぜならそのような道は、既に見出した「色1と色3の頂点のみを伝って $v_{1}$ と $v_{3}$ を結ぶ道」とどこかで交わらざるを得ないからである。

以上でグラフ $G$ が5色で塗り分けられることが判明した。

線形時間5彩色アルゴリズム

1996年、Robertson, Sanders, Seymour, Thomas は "Efficiently four-coloring planar graphs"^[1] の中で、マルチグラフ（英語版）に対する2次多項式時間4彩色アルゴリズムを記述し、同論文の中で彼らは単純平面グラフを線形時間で5色彩色するアルゴリズムについて手短に述べている。これは漸近最適（英語版）であり、また次に述べるウェルニッケの定理（Wernicke's Theorem）に基づく。

ウェルニッケの定理: グラフ

G

は平面的で、空集合でなく、2辺で囲まれるような面を持たず、かつ頂点の次数の最小値は5であるとする。このとき

G

には次数が5または6の頂点と隣接しているような次数5の頂点が存在する。

アルゴリズムは、グラフに対し次の2種類の操作を再帰的に用いることで彩色を行う。

次数が4以下である頂点を削除する（この頂点は隣接していた頂点が使っていない色で塗れる）。
次数が5で、かつ次数6以下の頂点と隣接しているような頂点を削除し、隣接していた5頂点の中から辺で結ばれていない2頂点を選び、1頂点に合併（merge）する（合併した2頂点は同じ色で、最初に削除した頂点は隣接していた頂点が使っていない色で塗れる）。

脚注

^ Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1996), “Efficiently four-coloring planar graphs”, Proc. 28th ACM Symposium on Theory of Computing (STOC), New York: ACM Press, http://people.math.gatech.edu/~thomas/PAP/fcstoc.pdf .