五色定理

グラフ理論における五色定理（ごしょくていり、）とは、領域に分けられた平面、例えばある州を郡に分けた政治地図が与えられたとき、5種類以下の色を使って、隣接する領域が必ず別の色になっているように各領域を塗り分けられるという定理である。
五色定理はそれより強い四色定理の系であるが、証明ははるかに易しく、1879年に（ケンペとも）が四色定理（予想）を証明し損ねたときの論法に基づき行える。は11年後にケンプの誤りを発見し、それを元に五色定理を証明した。
証明のアウトライン.
まず、与えられた地図に単純な平面グラフ formula_1 を対応させる。つまり、地図の各領域をグラフの頂点とし、2領域が隣接しているときかつそのときに限り、対応する2頂点を1つの辺で結ぶものとする。こうして問題はグラフの彩色問題に変換される：各頂点に色を塗って、どの辺についても端点である2頂点の色が一致しないようにできるか。
グラフ formula_1 は単純平面グラフである、つまり平面上にどの2辺も交差させることなく描くことができ、かつどの2頂点間にも2本以上の辺が存在せず、ループも存在しないので、平面のオイラー標数を用いることで、グラフ formula_1 には最大でも5本の辺によってしか接続されていないような頂点が存在することが証明できる（注意："五色定理の仮定（色の数が最大で5）が使われるのはこの箇所だけである。もし同じ手法で四色定理を証明しようとしても、この段階で頓挫する。実際、正二十面体グラフ（icosahedral graph）は5-正則な平面グラフであり、接続する辺が4本以下であるような頂点は存在しない"）。このような頂点を1つ選んで formula_4 と呼ぶことにする。
今、頂点 formula_4 を formula_1 から取り除く。このようにして得られるグラフ formula_7 は頂点の数がグラフ formula_1 よりも1個だけ少ないので、数学的帰納法により5色で彩色できるとしてよい。頂点 formula_4 は他の5個の頂点と隣接しているとする（4個以下であれば、隣接する頂点に使われていない色を塗ることでグラフ formula_1 の彩色は終わる）。そこでこれらの formula_4 と隣接していた5頂点を（反）時計回りに formula_12, formula_13, formula_14, formula_15, formula_16 とする（番号の振り方は formula_1 の描き方に依る）。もしこれらが5つの異なる色で塗られていなければ、明らかに頂点 formula_4 を使われていない色で塗ることでグラフの彩色が終わる。
そこで、頂点 formula_12, formula_13, formula_14, formula_15, formula_16 はそれぞれ色 1, 2, 3, 4, 5 で塗られていると仮定する。
グラフ formula_7 から、色1または3で塗られた頂点と、それらを接続する辺だけを取り出した部分グラフ formula_25 を考える。明らかにどの辺も色1の頂点と色3の頂点を結ぶ（これをという）。もし formula_12 と formula_14 とがグラフ formula_25 の異なる連結成分に属するならば、formula_12 が属す連結成分で色1と色3を交換することで、頂点 formula_4 を色1で塗ることができるようになり、証明が終わる。
そうでない場合、formula_12 と formula_14 とはグラフの同一の連結成分に属すことになるので、色1と色3の頂点のみを伝ってこれらを結ぶ formula_25 の道を見つけることができる。
ここで今度は、グラフ formula_7 から色2または4で塗られた頂点とそれらを接続する辺だけを取り出した部分グラフ formula_35 に目を向け、同じ議論を繰り返すことにする。すると、グラフ formula_35 の formula_13 を含む連結成分において色2と色4を交換することで頂点 formula_4 が色2で塗れるようになるか、色2と色4の頂点のみを伝って formula_13 と formula_15 を結ぶ formula_35 の道を見つけることができるかの、二つに一つである。ところが後者はあり得ない。なぜならそのような道は、既に見出した「色1と色3の頂点のみを伝って formula_12 と formula_14 を結ぶ道」とどこかで交わらざるを得ないからである。
以上でグラフ formula_1 が5色で塗り分けられることが判明した。
線形時間5彩色アルゴリズム.
1996年、Robertson, Sanders, Seymour, Thomas は "Efficiently four-coloring planar graphs" の中で、に対する2次多項式時間4彩色アルゴリズムを記述し、同論文の中で彼らは単純平面グラフを線形時間で5色彩色するアルゴリズムについて手短に述べている。これはであり、また次に述べるウェルニッケの定理（Wernicke's Theorem）に基づく。
アルゴリズムは、グラフに対し次の2種類の操作を再帰的に用いることで彩色を行う。