四色定理の紹介と五色定理の証明

平面的グラフ $G$ の全ての頂点の次数が $6$ 以上と仮定する。$G$ の頂点数，枝数，面の数をそれぞれ $|V|,|E|,|F|$ とする。

各頂点に $6$ 本以上枝が集まるので，$6|V|\leq 2|E|$

各面の境界に含まれる枝数は $3$ 以上なので $3|F|\leq 2|E|$

これらの不等式とオイラーの多面体定理より，

$2=|V|-|E|+|F|\\ \leq \dfrac{1}{3}|E|-|E|+\dfrac{2}{3}|E|=0$

となり矛盾。背理法により補題が示された。

$|V|=1$ のときは自明。以下，$|V|=k$ のときを仮定して $|V|=k+1$ のときを証明する。

$G$ には補題より次数 $5$ 以下の頂点が存在する，そのうちの一つを $v$ とする。$G$ から $v$ （および $v$ に接続する枝）を除いたグラフを $G'$ とする。帰納法の仮定により $G'$ は五彩色可能である。この彩色で $G$ の $v$ 以外の頂点を塗る。

(i) $v$ の次数が $5$ であり，その $5$ つの頂点が全て異なる色で塗られている場合：

$5$ つの頂点を $v_1,\cdots, v_5$ とし，各頂点の色を $c_1,\cdots,c_5$ とする。

$v_1$ から色 $c_1$ と $c_3$ で塗られた頂点のみをつたって行ける頂点の集合を $V_{13}$ と書く。

CASE1： $v_3\not\in V_{13}$ のとき，

$V_{13}$ の色 $c_1$ と $c_3$ をひっくり返せば彩色の条件を保ったまま $v$ の周りを四色にできる。 $v$ を $c_1$ で塗ればよい。

CASE2： $v_3\in V_{13}$ のとき，

$v_1$ から $v_3$ に $c_1$ と $c_3$ で塗られた頂点のみからなる道が存在する。

これと $G$ の平面性から，$v_2$ から $v_4$ に $c_2$ と $c_4$ で塗られた頂点のみからなる道は存在しない。

つまり，$v_2$ から色 $c_2$ と $c_4$ で塗られた頂点のみをつたって行ける頂点の集合 $V_{24}$ の色 $c_2$ と $c_4$ をひっくり返せば $v$ の周りが四色になる。 $v$ を $c_2$ で塗ればよい。

(ii) そうでない場合：

余った色で $v$ を塗ればよい。