四色定理
以下の議論はEvery Planar Map is Four Colorable (Appel & Haken 1989)の序論に基づく要約である。欠点はあるが、ケンペの4色定理の最初の証明とされるものは、後に4色定理の証明に使われる基本的なツールの一部を提供した。ここでの説明は、上記の現代グラフ理論の定式化の観点から言い直したものである。
ケンペの議論は次のようなものである。まず,グラフで区切られた平面領域が三角分割されていない場合,つまり,境界にちょうど3つの辺がない場合,境界のない外側の領域も含めてすべての領域を三角形にするために,新しい頂点を導入することなく辺を追加することができる.この三角化グラフが4色以下で着色可能であれば,辺を削除しても同じ着色法が成り立つので,元のグラフも同様である.したがって,三角形化されたグラフの4色定理を証明するには,すべての平面グラフについて証明すれば十分であり,一般性を損なうことなくグラフが三角形化されていると仮定する.
頂点、辺、領域(面)の数を v, e, f とする。各領域は三角形であり、各辺は2つの領域で共有されるので、2e=3fとなる。これはオイラーの多面体定理v- e + f = 2 を使えば、6v- 2e = 12.さて、頂点の次数とは、その頂点に接する辺の数である。v_nを次数nの頂点の数、Dを任意の頂点の最大次数とする、
6 v − 2 e = 6 ∑ i = 1 D v i − ∑ i = 1 D i v i = ∑ i = 1 D ( 6 − i ) v i = 12.