6-3 平面グラフの五色定理

辺 $xy$ を任意に取ります。
両端が $K$ の外なら色は変わりません。両端が $K$ 内なら、元の色は $a,b$ の異なる二色であり、両方を交換しても異なるままです。
ちょうど一端 $x$ が $K$ 内だとします。交換後の $x$ の色は $a$ または $b$ です。もし外側の端 $y$ が同じ色なら、$y$ も色 $a$ または $b$ であり、辺 $xy$ によって $x$ と同じ $G[a,b]$ の連結成分へ入ります。これは $y\notin K$ に反します。
従ってどの辺の両端も同色にならず、交換後もproperです。□

本巻第5章のEuler公式から
$$ |E|\le3|V|-6. $$
従って平均次数は
$$ \frac{1}{|V|}\sum_{v\in V}\deg(v) =\frac{2|E|}{|V|} \le6-\frac{12}{|V|} <6. $$
全頂点次数が6以上なら平均も6以上となるので矛盾します。従って次数5以下の頂点があります。□

$P$ をsimple pathとして取ります。$P$ は $v$ を含まず、辺 $vv_1,vv_3$ は $v$ 以外で互いにも $P$ にも交わりません。従って
$$ C=vv_1\cup P\cup v_3v $$
は単純cycleで、plane embedding上の単純閉曲線です。
$v$ の十分小さい円周上で、$vv_1,vv_2,vv_3,vv_4$ はこの順に横切ります。閉曲線 $C$ は円周を $vv_1$ と $vv_3$ の位置で横切るため、$vv_2$ の短い始部分と $vv_4$ の短い始部分は $C$ の異なる側にあります。辺は $C$ を横切れないので、頂点 $v_2,v_4$ も $C$ の異なる側にあります。
$G-v$ の $v_2$--$v_4$ pathは、一方の側から他方へ移るため、本巻第5章の交互端点定理により $C$ と交わらなければなりません。$v$ はpathに含まれず、plane graphの辺同士は内部で交差しないので、交点は $P$ 上の頂点です。従って $P$ と頂点非共有な $v_2$--$v_4$ pathは存在しません。□

平行辺は頂点彩色条件を変えないので一本にまとめ、simple graphとしてよいです。頂点数 $n=|V(G)|$ について帰納します。
$n\le5$ なら、各頂点へ異なる色を与えて高々5色で塗れます。
$n\ge6$ とし、plane embeddingを一つ固定します。low-degree lemmaにより次数5以下の頂点 $v$ を取れます。帰納法から $G-v$ は色集合 $\{1,2,3,4,5\}$ でproperに塗れます。
$\deg(v)\le4$ なら、近傍が使う色は高々4色なので、使われていない色を $v$ へ与えられます。$\deg(v)=5$ でも、五近傍が使う色が4色以下なら同じです。
残る場合、$v$ は相異なる五近傍をもち、それらが五色を一度ずつ使っています。plane embeddingにおける巡回順に
$$ v_1,v_2,v_3,v_4,v_5 $$
と名付け、色名を付け替えて
$$ \varphi(v_i)=i \qquad(1\le i\le5) $$
としてよいです。
$G-v$ の二色部分graph $G[1,3]$ を考えます。$v_1$ と $v_3$ が異なるKempe componentに属するなら、$v_1$ を含む成分だけで色1と3を交換します。Kempe swap lemmaによりproper coloringは保たれ、$v$ の近傍から色1が消えます。そこで $v$ を色1にすれば彩色を拡張できます。
従って、残るのは $v_1,v_3$ が同じ1--3 Kempe componentに属する場合です。この成分内にsimple $v_1$--$v_3$ path $P_{13}$ があります。
次に $G[2,4]$ を考えます。もし $v_2,v_4$ が同じ2--4 Kempe componentに属するなら、内部が色2または4だけからなるsimple path $P_{24}$ があります。色集合が互いに素なので $P_{13}$ と $P_{24}$ は頂点を共有しません。しかし近傍は
$$ v_1,v_2,v_3,v_4 $$
の巡回順にあり、alternating neighbours separation lemmaはそのような二pathの共存を禁止します。矛盾です。
従って $v_2,v_4$ は異なる2--4 Kempe componentに属します。$v_2$ を含む成分だけで色2と4を交換すると、proper coloringを保ったまま $v$ の近傍から色2が消えます。$v$ を色2にして彩色を拡張できます。
全ての場合に $G-v$ の5-coloringを $G$ へ拡張できました。帰納法により全planar graphは5-colorableです。□

境界辺 $xy$ で $x$ がcomponent内、$y$ が外だとします。交換後の $x$ と $y$ が同色になるなら、$y$ の色もredまたはblueです。すると $xy$ はred--blue誘導部分graphの辺であり、$y$ は $x$ と同じ連結成分へ入るはずです。これは $y$ がcomponent外という仮定に反します。従って境界で衝突しません。□

近傍では色5が使われていません。従って $v$ を色5にすれば、全ての隣接頂点と異なる色になりproper coloringが得られます。Kempe交換が必要なのは五近傍が五色を一度ずつ使う場合だけです。□

1--3 path $P_{13}$ と二辺 $vv_1,vv_3$ は単純閉曲線を作り、巡回順から $v_2,v_4$ はその反対側にあります。2--4 pathがあればこの曲線を横切る必要があります。
pathは $v$ を使わず、plane embeddingの辺は内部で交差しないので、交点は $P_{13}$ の頂点でなければなりません。しかし1--3 pathの頂点色は1または3、2--4 pathでは2または4なので頂点共有は不可能です。従って2--4 pathは存在しません。□

共通条件は「$v$ の近傍で使われている色が高々4色」であることです。次数4以下なら近傍頂点数自体が4以下なのでこの条件を満たします。次数5でも色が重複すれば異なる近傍色数は4以下です。
いずれも五色のうち少なくとも一色が近傍で未使用なので、その色を $v$ へ与えれば帰納的彩色を拡張できます。□

奇cycleは3色必要で、3色で塗れます。中心はrimの全頂点と隣接するため、その3色のどれも使えず第四色が必要です。従ってwheelは4-colorableであり、
$$ \chi(W_{2m+2})=4. $$
これは平面graphで五色上界が常に鋭いわけではないことを示します。□

「平面双対」から、bridgeに対応するdual edgeだけがloopです。元graphにbridgeがないのでdual $G^*$ はloopless planar graphです。五色定理により $G^*$ の頂点を高々五色でproperに塗れます。
$G^*$ の頂点は元graphの面で、dualで隣接する二頂点は元graphで辺を共有する二面です。従ってdual頂点の色を対応する面へ移せば、辺を共有する面が異色となる五色面彩色を得ます。□