五色定理

$v$ の隣接頂点 $w_1,\dots,w_5$ がどの 2 つも隣接するなら、$w_1,\dots,w_5$ は完全グラフ $K_5$ を部分グラフとして含む。$K_5$ は平面グラフでなく（平面グラフ の記事の命題「$K_5$ は平面グラフでない」）、平面グラフの部分グラフは平面グラフなので、矛盾する。$\square$

頂点数 $n$ についての帰納法で示す。$n\le5$ なら各頂点に異なる色を与えればよい。$n\ge6$ とし、頂点数が $n$ より少ない平面グラフは 5-頂点彩色をもつとする。$G$ には次数 $5$ 以下の頂点 $v$ がある。
$v$ の次数が $4$ 以下のとき：$G-v$ は平面グラフなので帰納法の仮定により 5-頂点彩色 $c$ をもつ。$v$ の隣接頂点が使う色は 4 色以下なので、残る色を $v$ に与えれば $G$ の 5-頂点彩色になる。
$v$ の次数が $5$ のとき：lem-fct-nonadjacent により、隣接しない $v$ の隣接頂点 $u,w$ がある。$U:=\{u,v,w\}$ は道 $u\,v\,w$ により連結である。$G$ から $U$ を 1 つの新しい頂点 $z$ につぶしたグラフ $G/U$（$U$ のどれかに隣接していた $U$ の外の頂点を $z$ に隣接させる）は、$\{U\}$ と残りの各頂点の 1 点集合を分岐集合として $G$ のマイナーであり、Kuratowskiの定理 の記事の系「マイナーをとる操作と平面性」により平面グラフである。$G/U$ の頂点数は $n-2$ なので、帰納法の仮定により 5-頂点彩色 $c'$ をもつ。
$G-v$ の頂点に色 $c(u):=c(w):=c'(z)$、それ以外の $x$ に $c(x):=c'(x)$ を与える。これは $G-v$ の 5-頂点彩色である。実際、$G-v$ の辺 $xy$ について、$x,y$ がともに $u,w$ 以外なら $xy$ は $G/U$ の辺である。$x=u$ なら $y\ne w$（$u,w$ は隣接しない）で、$y$ は $G/U$ で $z$ に隣接するので $c(y)=c'(y)\ne c'(z)=c(u)$ である。$x=w$ のときも同じである。
$v$ の 5 つの隣接頂点のうち $u,w$ は同じ色なので、隣接頂点が使う色は 4 色以下であり、残る色を $v$ に与えれば $G$ の 5-頂点彩色が得られる。$\square$

$\lvert G\rvert$ についての帰納法で示す。$v_1,v_2$ の色を $c(v_1),c(v_2)$ とする。
$\lvert G\rvert=3$ のとき、$G$ は三角形 $v_1v_2v_3$ で、$L(v_3)$ は 3 色以上なので $c(v_1),c(v_2)$ 以外の色を $v_3$ に塗ればよい。
$\lvert G\rvert\ge4$ で $C$ に弦 $vw$ があるとき：(T2) の $C_1,C_2$ を、$C_1$ が辺 $v_1v_2$ を含み $C_2$ が含まないようにとる。$C_2$ は $C$ の頂点で $C_1$ にないものを含むので $\lvert G_1\rvert<\lvert G\rvert$ であり、$G_1$ は仮定を満たす（$C_1$ の $v_1,v_2$ 以外の頂点は $C$ の頂点か $v,w$ で、リストは 3 色以上）。帰納法の仮定により $G_1$ をリストから塗る。$v,w$ は隣接するので異なる色をもつ。次に $G_2$ に、$C_2$ で隣り合う $v,w$ を $v_1,v_2$ の役として帰納法の仮定を使う。$C_2$ の $v,w$ 以外の頂点は、$C$ を $v,w$ で切った 2 つの弧のうち $v_1v_2$ を含まない方の内部にあるので $v_1,v_2$ とは異なり、リストは 3 色以上である。$\lvert G_2\rvert<\lvert G\rvert$ なので $G_2$ も $v,w$ の色を延長して塗れる。$G$ の辺は $G_1$ か $G_2$ の辺なので、2 つの彩色を合わせたものは $G$ の彩色である。
$\lvert G\rvert\ge4$ で $C$ に弦がないとき：(T3) の記号を使う。$L(v_k)$ は 3 色以上なので、$c(v_1)$ と異なる 2 色 $j,\ell\in L(v_k)$ がとれる。各 $u_i$ のリストから $j,\ell$ を除く。$u_i$ は $C$ の上にないのでリストは 5 色以上あり、除いたあとも 3 色以上残る。$G-v_k$ は外周 $C'$ に沿って $v_1,v_2$ が隣り合い（$C-v_k$ は道 $v_1v_2\cdots v_{k-1}$）、$C'$ の $v_1,v_2$ 以外の頂点のリストは 3 色以上、$C'$ の上にない頂点のリストは 5 色以上なので、帰納法の仮定により $v_1,v_2$ の色を $G-v_k$ の彩色に延長できる。$v_k$ の隣接頂点は $v_1$（色は $j,\ell$ でない）、$u_i$（色は $j,\ell$ でない）、$v_{k-1}$ だけなので、$j,\ell$ のうち $v_{k-1}$ の色でない方を $v_k$ に塗れば $G$ の彩色になる。$\square$

平面グラフ $G$ と、各頂点の 5 色のリスト $L$ をとる。$\lvert G\rvert\le2$ なら、隣接頂点の色を避けて順に塗ればよい。$\lvert G\rvert\ge3$ なら、$G$ の平面グラフ図に辺を加えられるだけ加えたもの $G^\ast$ を作る。(T1) により $G^\ast$ のすべての面の境界は三角形であり、外側の面の境界を $v_1v_2v_3v_1$ とする。$v_1$ に $L(v_1)$ の色を、$v_2$ に $L(v_2)$ の色で $v_1$ と異なるものを塗り、lem-fct-thomassen-strong を $G^\ast$ に使えば、$G^\ast$ のリストからの彩色が得られる。$G$ は $G^\ast$ の部分グラフなので、これは $G$ のリストからの彩色でもある。$\square$