§E16.21五色定理

(1)を示す。$P$が$v_2$または$v_4$を通るならば、その頂点は$Q$の端点でもあるから、$P$と$Q$の共通の頂点である。以下、$P$は$v_2$も$v_4$も通らないとする。

$P$を描く曲線に辺$v v_1$と辺$v v_3$を描く曲線を継ぎ足した閉曲線を$C$とする。$P$は道であるから頂点が相異なり、$P$は$G - v$の道であるから$v$を通らない。埋め込みでは相異なる辺が共通の端点以外で交わらないので、$C$は単純閉曲線である。$C$の上にある頂点は$v$と$P$の頂点だけであるから、$v_2$と$v_4$は$C$の上に無い。

注意 1.2 (2)により、$v$の十分近くでは辺$v v_1$と辺$v v_3$が$v$のまわりを二つの部分に分け、巡回順序で$v v_1$と$v v_3$のあいだにある辺は一方の部分へ、そうでない辺は他方の部分へ出る。$v_1, v_2, v_3, v_4$はこの順に現れるので、辺$v v_2$は$v v_1$と$v v_3$のあいだにあり、辺$v v_4$はあいだにない。$v$の十分小さい近傍の中で$C$に属する点は辺$v v_1$と辺$v v_3$の点だけであるから、二つの部分はその近傍から$C$を除いた集合であり、注意 1.2 (1)の局所的な分離により、一方は$C$の内側に、他方は外側に属する。辺$v v_2$は、$v_2 \ne v_1, v_3$であるから辺$v v_1$、辺$v v_3$と異なり、$v$を端点にもつので$P$の辺とも異なる。$v_2$は$C$の上に無いので、辺$v v_2$が$C$と共有する点は$v$だけである。辺$v v_4$についても同じである。ゆえに、辺$v v_2$から$v$を除いた部分と、辺$v v_4$から$v$を除いた部分は、それぞれ連結で$C$と交わらず、平面から$C$を除いた集合の一つの連結成分に含まれる。したがって$v_2$と$v_4$は$C$の異なる側にある。

$Q$を描く曲線は$C$の内側の点と外側の点を結ぶので、注意 1.2 (1)により$C$と少なくとも一点を共有する。$Q$は$G - v$の道であるから$v$を通らず、辺$v v_1$と辺$v v_3$を用いない。埋め込みでは相異なる辺が共通の端点以外で交わらず、相異なる頂点は相異なる点に描かれているので、共有する点は$Q$と$P$に共通する頂点であるか、$Q$と$P$に共通する辺の点である。後者の場合にも、その辺の端点は$Q$と$P$に共通する頂点である。ゆえに$P$と$Q$は共通の頂点をもつ。

場合 2-b では、$v$の隣接頂点$v_1, v_2, v_3, v_4$は巡回順序でこの順に現れ、$P$は$G_{1,3}$の中の$v_1$から$v_3$への道であるから、$P$の頂点の色は$1$または$3$である。$v_4 \in H'$と仮定すると、$G_{2,4}$の中の$v_2$から$v_4$への道$Q$が存在し、その頂点の色は$2$または$4$である。前段により$P$と$Q$は共通の頂点をもつが、その頂点の色は$\{1, 3\}$と$\{2, 4\}$の両方に属することになり、矛盾する。ゆえに$v_4 \notin H'$である。

(2)を示す。$G$の平面埋め込みを一つ固定する。色は$1, 2, 3, 4$とする。$v$の隣接頂点に現れる色が$3$種類以下ならば、現れない色を$v$へ与えれば$G$の$4$-彩色が得られる。

$v$の隣接頂点に$4$色すべてが現れるとする。注意 1.2 (2)により、$v$における辺の巡回順序に沿って隣接頂点を$v_1, v_2, v_3, v_4$と並べ、色の番号を付け替えて$c(v_t) = t$（$t = 1, 2, 3, 4$）としてよい。$c$に関する$(1, 3)$-Kempe 鎖のうち$v_1$を含むものを$H$とする。

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

$v_3 \in H$のとき、$H$は連結であるから、$G_{1,3}$の中に$v_1$から$v_3$への道$P$が存在する。$c$に関する$(2, 4)$-Kempe 鎖のうち$v_2$を含むものを$H'$とし、$v_4 \in H'$と仮定すると、$G_{2,4}$の中に$v_2$から$v_4$への道$Q$が存在する。$P$と$Q$は$G - v$の道であり、$v_1, v_2, v_3, v_4$は巡回順序でこの順に現れるので、(1)により$P$と$Q$は共通の頂点をもつ。しかし$P$の頂点の色は$1$または$3$、$Q$の頂点の色は$2$または$4$であるから、これは起こらない。ゆえに$v_4 \notin H'$である。補題 2.2により、$H'$の上で色$2$と色$4$を入れ替えた割り当て$c''$は$G - v$の$4$-彩色であり、$c''(v_2) = 4 = c''(v_4)$であって、$v_1$と$v_3$の色は変わらない。ゆえに$c''$のもとで$v$の隣接頂点に現れる色は$\{1, 3, 4\}$であり、$v$へ色$2$を与えれば$G$の$4$-彩色が得られる。

(3)では、例 3.2の車輪グラフ$W$と、同じ例の$W - v$の$5$-彩色$c(v_t) = t$を用いる。$W$は単純平面的グラフであり、$\deg_W(v) = 5$、$v$における巡回順序は$v_1, \dots, v_5$である。

$t \in \{1, \dots, 5\}$を固定し、$t+1$を$5$を法として読む。$W - v$で色が$t$または$t+1$である頂点は$v_t$と$v_{t+1}$だけであるから、$G_{t,t+1}$はこの二頂点が誘導する部分グラフである。$W - v$は閉路$v_1 v_2 v_3 v_4 v_5 v_1$であり、辺$v_t v_{t+1}$をもつので、$G_{t,t+1}$は連結である。ゆえに$v_t$を含む$(t, t+1)$-Kempe 鎖は$\{v_t, v_{t+1}\}$であり、$v_{t+1}$を含む。

この Kempe 鎖の上で色$t$と色$t+1$を入れ替えると、$v_t$の色は$t+1$、$v_{t+1}$の色は$t$になり、他の隣接頂点の色は変わらない。したがって入れ替えの後も$v$の隣接頂点に現れる色は$\{1, 2, 3, 4, 5\}$のままであり、$v$へ与える色は得られない。巡回順序で隣り合う二つの隣接頂点を結ぶ道からは、(1)のように残りの隣接頂点を隔てる単純閉曲線が得られない。定理 3.1の証明が$(1, 3)$と$(2, 4)$のように巡回順序で隣り合わない組を用いるのはこのためである。この例でも、$v_1$を含む$(1, 3)$-Kempe 鎖は$\{v_1\}$であり、場合 2-a により$v$へ色$1$を与えることができる。

(4)を示す。入れ替えた割り当てを$c'$とし、$G$の辺$xy$をとる。

$x, y \in U$のとき、$c(x), c(y) \in \{i, j\}$であり、$c'(x)$と$c'(y)$は$c(x)$と$c(y)$に色$i$と色$j$の入れ替えという単射を施したものである。$c(x) \ne c(y)$であるから$c'(x) \ne c'(y)$である。$x, y \notin U$のとき、$c'(x) = c(x) \ne c(y) = c'(y)$である。

$x \in U$、$y \notin U$のとき、$c'(x) \in \{i, j\}$である。$c(y) \in \{i, j\}$と仮定すると、$y$は$G_{i,j}$の頂点であり、$G_{i,j}$は誘導部分グラフであるから辺$xy$は$G_{i,j}$の辺である。したがって$y$は$x$を含む$G_{i,j}$の連結成分に属する。$U$は連結成分の頂点集合の合併であり$x \in U$であるから、$x$を含む連結成分の頂点はすべて$U$に属し、$y \in U$となって矛盾する。ゆえに$c(y) \notin \{i, j\}$であり、$c'(y) = c(y) \ne c'(x)$である。$x \notin U$、$y \in U$のときも同じである。以上より$c'$は$G$の彩色である。用いる色の集合は増えない。$U$が一つの連結成分の頂点集合のとき、これは補題 2.2である。

例として、道$P_3$の頂点を$x_1, x_2, x_3$、辺を$x_1 x_2$、$x_2 x_3$とし、$2$-彩色$c(x_1) = 1$、$c(x_2) = 2$、$c(x_3) = 1$を考える。$i = 1$、$j = 2$とすると、$G_{1,2}$は$P_3$全体であり、連結成分はそれ自身だけである。$U = \{x_1, x_3\}$とすると、$U$は連結成分の頂点集合の合併ではない。$U$の上で色$1$と色$2$を入れ替えると$c'(x_1) = c'(x_2) = c'(x_3) = 2$となり、辺$x_1 x_2$の両端点の色が等しいので、$c'$は$P_3$の彩色ではない。$U = \{x_1\}$としても、$U$は連結な部分グラフの頂点集合であるが連結成分の頂点集合ではなく、$c'(x_1) = 2 = c'(x_2)$となるので、$c'$は彩色ではない。

(5)を示す。$n \ge 3$とし、辺の本数を$m$とする。§D2.12 系 3.4より$m \le 3n - 6$であり、§D2.7 定理 1.2より$\sum_{v \in V}\deg_G(v) = 2m$であるから

である。$n \le 2$では成り立たない例として、一頂点のグラフでは左辺は$6$であり、二頂点を一本の辺で結んだグラフでは左辺は$5 + 5 = 10$である。

最小次数が$3$以上の単純平面的グラフ$G$をとる。各頂点は自分以外の$3$個以上の頂点と隣接するので$n \ge 4$であり、前段の不等式が成り立つ。次数が$6$以上の頂点の項$6 - \deg_G(v)$は$0$以下であり、次数が$5$以下の頂点の項は、次数が$3$以上であるから$3$以下である。次数が$5$以下の頂点の個数を$k$とすると