§E13.21五色定理

証明.$G$の頂点の個数を$n$、辺の本数を$m$と書く。

$n \le 2$のときは、$G$が単純なので各頂点の次数は$1$以下であり、主張が成り立つ。

$n \ge 3$とする。§D2.12 系 3.4により$m \le 3n - 6$である。握手補題（§D2.7 定理 1.2）により

が成り立つ。すべての頂点の次数が$6$以上であると仮定すると$\sum_{v \in V} \deg_G(v) \ge 6n$となり、この不等式に反する。よって次数が$5$以下の頂点が存在する。▨

証明.$G$の辺$uv$をとり、$c'(u) \ne c'(v)$を示す。

$u$と$v$がともに$H$に属する場合を考える。$c'$は$c$の値に色$i$と色$j$の入れ替えという単射を施したものであるから、$c(u) \ne c(v)$より$c'(u) \ne c'(v)$が従う。

$u$と$v$がともに$H$に属さない場合を考える。$c'(u) = c(u)$かつ$c'(v) = c(v)$であるから$c'(u) \ne c'(v)$である。

$u \in H$かつ$v \notin H$の場合を考える。$u \in H$より$c(u) \in \{i, j\}$であり、色の入れ替えののちも$c'(u) \in \{i, j\}$である。ここで$c(v) \in \{i, j\}$であると仮定すると、$v$は$G_{i,j}$の頂点であり、辺$uv$は$G_{i,j}$の辺であるから、$H$が$G_{i,j}$の連結成分であることにより、$v$は$u$と同じ連結成分、すなわち$H$に属する。これは$v \notin H$に反する。よって$c(v) \notin \{i, j\}$であり、$c'(v) = c(v) \notin \{i, j\}$である。$c'(u) \in \{i, j\}$であるから$c'(u) \ne c'(v)$である。

$u \notin H$かつ$v \in H$の場合には、$u$と$v$の役割を入れ替えて同じ議論を行えばよい。

用いる色については、$c'$の値の全体は$c$の値の全体に含まれるので増えない。▨

証明. 頂点の個数$n$についての累積帰納法（§D2.1 命題 1.2）で示す。

$n \le 5$のときは、すべての頂点に相異なる色を与えれば$5$色以下で正しい彩色になる。

$n \ge 6$とし、頂点の個数が$n$より少ないどの単純平面的グラフも$5$-彩色可能であると仮定する。$G$を頂点の個数が$n$の単純平面的グラフとし、平面埋め込みを一つ固定する。補題 1.1により、$\deg_G(v) \le 5$である頂点$v$をとる。注意 1.2 (3)により$G - v$は平面的であり、頂点の個数は$n - 1$である。帰納法の仮定により$G - v$の$5$-彩色$c$が存在する。色は$1, 2, 3, 4, 5$とする。

場合 1.$v$の隣接頂点に現れる色が$4$種類以下であるとする。現れない色が少なくとも一つあるので、その色を$v$へ与えれば$G$の$5$-彩色が得られる。$\deg_G(v) \le 4$のときは必ずこの場合になる。

場合 2.$\deg_G(v) = 5$であり、隣接頂点に$5$色すべてが現れるとする。注意 1.2 (2)により、$v$における辺の巡回順序に沿って隣接頂点を$v_1, v_2, v_3, v_4, v_5$と並べる。仮定より五つの隣接頂点の色はすべて相異なるので、色の番号を付け替えることにより、$c(v_t) = t$（$t = 1, \dots, 5$）としてよい。

$G - v$の彩色$c$に関する$(1, 3)$-Kempe 鎖のうち、$v_1$を含むものを$H$とする。

場合 2-a.$v_3 \notin H$とする。補題 2.2により、$H$の上で色$1$と色$3$を入れ替えて得られる割り当て$c'$も$G - v$の$5$-彩色である。$v_1 \in H$であるから$c'(v_1) = 3$であり、$v_3 \notin H$であるから$c'(v_3) = 3$のままである。$v_2, v_4, v_5$の色は$\{1, 3\}$に属さないので、$H$に属するかどうかによらず変わらない。したがって$c'$のもとで$v$の隣接頂点に現れる色は$3, 2, 3, 4, 5$、すなわち$\{2, 3, 4, 5\}$であり、色$1$が現れない。$v$へ色$1$を与えれば$G$の$5$-彩色が得られる。

場合 2-b.$v_3 \in H$とする。$H$は連結であるから、$G_{1,3}$の中に$v_1$から$v_3$への道$P$が存在する。$P$の頂点の色はすべて$1$または$3$である。ここで$c(v_2) = 2$かつ$c(v_4) = 4$であるから、$v_2 \notin P$かつ$v_4 \notin P$ である。この二つを先に確かめておく。

固定した平面埋め込みにおいて、$P$を描く曲線に、辺$v v_1$と辺$v v_3$を描く曲線を継ぎ足すと、平面上の閉曲線$C$が得られる。$P$は道なので頂点が相異なり、$v$は$G - v$の頂点ではないので$P$の上に無い。また埋め込みでは辺どうしが端点以外で交わらないので、$C$は単純閉曲線である。$C$の上にある頂点は$v$と$P$の頂点だけであるから、直前に確かめたことにより$v_2$も$v_4$も$C$の上に無い。

注意 1.2 (2)により、$v$の十分近くでは辺$v v_1$と辺$v v_3$が$v$のまわりを二つの部分に分け、巡回順序で$v_1$と$v_3$のあいだにある$v_2$への辺は一方の部分へ、$v_4$と$v_5$への辺は他方の部分へ出る。$v$の十分小さい近傍の中で$C$に属する点は、辺$v v_1$と辺$v v_3$の点だけであるから、この二つの部分は、その近傍から$C$を除いた集合にほかならない。$v$は$C$の上の点であるので、注意 1.2 (1)の局所的な分離により、その集合は内側に属する部分と外側に属する部分の二つへ分かれる。したがって、$v$の近くにおいて$v_2$へ向かう辺の点と$v_4$へ向かう辺の点は、$C$の内側と外側に分かれる。

辺$v v_2$は、$C$を構成する辺$v v_1$、辺$v v_3$、および$P$の各辺のいずれとも異なる。埋め込みでは相異なる辺が共通の端点以外で交わらず、$v_2$が$C$の上に無いので、辺$v v_2$が$C$と共有する点は$v$だけである。辺$v v_4$についても、$C$を構成するどの辺とも異なり、$v_4$が$C$の上に無いので、$C$と共有する点は$v$だけである。よって、辺$v v_2$から端点$v$を除いた部分は連結で$C$と交わらず、平面から$C$を除いた集合の一つの連結成分に含まれる。辺$v v_4$についても同じことが成り立つ。前段で二つの辺が$v$の近くで内側と外側に分かれることを見たので、$v_2$は$C$の一方の側にあり、$v_4$は他方の側にある。

いま、$c$に関する$(2, 4)$-Kempe 鎖のうち$v_2$を含むものを$H'$とし、$v_4 \in H'$であると仮定する。すると$G_{2,4}$の中に$v_2$から$v_4$への道$Q$が存在する。$Q$を描く曲線は、$C$の内側の点と外側の点を結ぶので、注意 1.2 (1)により$C$と少なくとも一点を共有する。埋め込みでは相異なる辺が端点以外で交わらず、相異なる頂点は相異なる点に描かれているので、共有する点は$Q$と$C$に共通する頂点でなければならない。$C$の頂点は$v$と$P$の頂点である。$Q$は$G - v$の道であるから$v$を通らない。$P$の頂点の色は$1$または$3$、$Q$の頂点の色は$2$または$4$であるから、共通の頂点は存在しない。これは矛盾である。よって$v_4 \notin H'$である。

補題 2.2により、$H'$の上で色$2$と色$4$を入れ替えて得られる割り当て$c''$も$G - v$の$5$-彩色である。$c''(v_2) = 4$であり、$v_4 \notin H'$より$c''(v_4) = 4$のままである。$v_1, v_3, v_5$の色は$\{2, 4\}$に属さないので変わらない。したがって$c''$のもとで$v$の隣接頂点に現れる色は$\{1, 3, 4, 5\}$であり、色$2$が現れない。$v$へ色$2$を与えれば$G$の$5$-彩色が得られる。

いずれの場合も$G$の$5$-彩色が得られたので、累積帰納法により、すべての単純平面的グラフは$5$-彩色可能である。▨