§E16.8彩色多項式

証明.主張 (1)を示す。$e$をループとし、$w=u_e=v_e$と置く。$c\colon V\to\{1,\dots,k\}$が正則な彩色であれば、辺$e$について$c(u_e)\ne c(v_e)$、すなわち$c(w)\ne c(w)$が成り立たなければならない。これはどの写像$c$についても成り立たない。ゆえに正則な彩色は存在せず、その個数は$0$である。

主張 (2)を示す。$G$と$G'$は頂点集合が同じであり、$G'$の辺は$G$の辺でもある。$c$を$G$の正則な彩色とすると、$G'$のすべての辺について条件が成り立つから、$c$は$G'$の正則な彩色である。逆に$c$を$G'$の正則な彩色とし、$e$を$G$の任意の辺とする。$G'$の構成より、$\{u_f,v_f\}=\{u_e,v_e\}$を満たす$G'$の辺$f$が存在する。$c$は$f$について条件を満たすから$c(u_e)\ne c(v_e)$である。ゆえに$c$は$G$の正則な彩色である。二つの集合が一致するので、その元の個数も一致する。▨

証明.$G-e$は$G$と同じ頂点集合をもち、辺集合が$E$の部分集合であるから単純グラフであり、辺数は$m-1$である。

$G/e$について、まずループが生じないことを示す。$f\in E\setminus\{e\}$について$\pi(x_f)=\pi(y_f)$が成り立つとすると、$\pi$の定義より$x_f\ne y_f$を満たすのは$\{x_f,y_f\}=\{u,v\}$の場合に限る。$G$は単純グラフであるから$u$と$v$を結ぶ辺は$e$だけであり、$f\ne e$に矛盾する。ゆえに$G/e$はループをもたない。平行な辺は定義において一本へまとめているから、$G/e$は単純グラフである。

頂点数は$\lvert V/e\rvert=(n-2)+1=n-1$である。辺集合は$E\setminus\{e\}$の各元へ端点の対を対応させた結果を集めたものであるから、その個数は$\lvert E\setminus\{e\}\rvert=m-1$以下である。▨

証明.$k$を正の整数とし、$\mathcal X$を$G-e$の$k$色による正則な彩色の全体とする。$\mathcal X_1=\{c\in\mathcal X:\ c(u)\ne c(v)\},\qquad\mathcal X_2=\{c\in\mathcal X:\ c(u)=c(v)\}$と置く。二つは互いに素であり、合併は$\mathcal X$に等しい。ゆえに§D2.2 定理 2.1より$\chi(G-e;k)=\lvert\mathcal X_1\rvert+\lvert\mathcal X_2\rvert$である。

$\lvert\mathcal X_1\rvert=\chi(G;k)$であること.$G$の辺集合は$E$であり、$G-e$の辺集合は$E\setminus\{e\}$である。写像$c\colon V\to\{1,\dots,k\}$が$G$の正則な彩色であることは、$E\setminus\{e\}$のすべての辺について条件が成り立ち、かつ辺$e$について$c(u)\ne c(v)$が成り立つことと同値である。これはちょうど$c\in\mathcal X_1$であることを意味する。

$\lvert\mathcal X_2\rvert=\chi(G/e;k)$であること.$\mathcal Y$を$G/e$の$k$色による正則な彩色の全体とし、写像$\Phi\colon\mathcal Y\to\{c\colon V\to\{1,\dots,k\}\},\qquad\Phi(c')=c'\circ\pi$を考える。$\pi$は定義 2.1の写像である。

まず$\Phi(c')\in\mathcal X_2$を示す。$c=c'\circ\pi$と置くと$c(u)=c'(w)=c(v)$である。$f\in E\setminus\{e\}$の端点を$x_f,y_f$とすると、$\{\pi(x_f),\pi(y_f)\}$は$G/e$のある辺の端点の対であるから、$c'$が正則であることより$c'(\pi(x_f))\ne c'(\pi(y_f))$、すなわち$c(x_f)\ne c(y_f)$である。ゆえに$c$は$G-e$の正則な彩色であり、$c(u)=c(v)$を満たすから$c\in\mathcal X_2$である。

$\Phi$は単射である。実際、$\pi$は全射であるから、$c'\circ\pi$が定まれば$c'$の各点での値が定まる。

$\Phi$は$\mathcal X_2$の上への全射である。$c\in\mathcal X_2$をとり、$c'(w)=c(u)=c(v),\qquad c'(x)=c(x)\ \ (x\in V\setminus\{u,v\})$によって$c'\colon V/e\to\{1,\dots,k\}$を定めると、定義から$c'\circ\pi=c$である。$c'$が$G/e$の正則な彩色であることを示す。$G/e$の任意の辺は、ある$f\in E\setminus\{e\}$について$\{\pi(x_f),\pi(y_f)\}$を端点の対にもつ。$c$は$G-e$の正則な彩色であるから$c(x_f)\ne c(y_f)$であり、$c'(\pi(x_f))=c(x_f)$かつ$c'(\pi(y_f))=c(y_f)$であるから$c'(\pi(x_f))\ne c'(\pi(y_f))$である。ゆえに$c'\in\mathcal Y$であり、$\Phi(c')=c$である。

以上より$\Phi$は$\mathcal Y$から$\mathcal X_2$への全単射であり、§D2.2 命題 1.5より$\lvert\mathcal X_2\rvert=\lvert\mathcal Y\rvert=\chi(G/e;k)$である。

したがって$\chi(G-e;k)=\chi(G;k)+\chi(G/e;k)$であり、移項して主張を得る。▨

証明. まず、次の主張を次数$d$についての累積帰納法（§D2.1 命題 1.2）で示す。

次数$d$の零でない多項式$g$に対し、$g(a)=0$を満たす有理数$a$は高々$d$個である。

$d=0$のとき$g$は零でない定数であるから、$g(a)=0$を満たす$a$は存在しない。

$d\ge1$とする。$g(a)=0$を満たす$a$が存在しなければ主張は成り立つ。存在するとして、その一つを$a$とする。$j\ge1$に対する恒等式$X^{j}-a^{j}=(X-a)\sum_{i=0}^{j-1}a^{\,j-1-i}X^{i}$を$g(X)=\sum_{j=0}^{d}c_jX^{j}$の各項へ適用すると、$g(a)=0$より$g(X)=g(X)-g(a)=\sum_{j=0}^{d}c_j\left(X^{j}-a^{j}\right)=(X-a)\,q(X),\qquad q(X)=\sum_{j=1}^{d}c_j\sum_{i=0}^{j-1}a^{\,j-1-i}X^{i}$と書くことができる。$q$における$X^{d-1}$の係数は$j=d$、$i=d-1$の項だけから生じて$c_d$に等しく、$c_d\ne0$であるから$q$は次数$d-1$の零でない多項式である。$b\ne a$が$g(b)=0$を満たすならば$(b-a)q(b)=0$かつ$b-a\ne0$であるから$q(b)=0$である。帰納法の仮定より$q(b)=0$を満たす$b$は高々$d-1$個であるから、$g(a)=0$を満たす$a$は高々$d$個である。

さて$h$が零多項式ではないとし、その次数を$d$とする。上の主張より$h(a)=0$を満たす有理数$a$は高々$d$個である。しかし仮定より$h$はすべての正の整数でこの条件を満たし、正の整数は無限に存在するから、矛盾である。ゆえに$h$は零多項式である。▨

証明. 一意性.$p$と$q$がともに条件を満たすとすると、多項式$h=p-q$はすべての正の整数$k$に対し$h(k)=\chi(G;k)-\chi(G;k)=0$を満たす。補題 4.1より$h$は零多項式であり、$p=q$である。

存在. 辺数$m=\lvert E\rvert$についての累積帰納法（§D2.1 命題 1.2）で示す。

$m=0$のとき、辺についての条件は空であるから、$V$から$\{1,\dots,k\}$への写像はすべて正則な彩色である。§D2.2 定理 2.3より、その個数は$k^{n}$である。$p_G(X)=X^{n}$と置けば、これは次数$n$のモニック整数係数多項式である。

$m\ge1$とし、辺数が$m$より小さいすべての有限単純無向グラフについて主張が成り立つと仮定する。辺$e=uv\in E$を一つ取る。辺が存在するので$n\ge2$である。命題 2.2より、$G-e$は$n$頂点$m-1$辺の単純グラフ、$G/e$は$n-1$頂点で辺数が$m-1$以下の単純グラフである。$n-1\ge1$であるから、いずれにも帰納法の仮定を適用することができ、次数$n$のモニック整数係数多項式$p_{G-e}$と次数$n-1$のモニック整数係数多項式$p_{G/e}$が存在する。

$p_G=p_{G-e}-p_{G/e}$と置く。整数係数多項式の差であるから$p_G$は整数係数である。$\deg p_{G-e}=n>n-1=\deg p_{G/e}$であるから、$p_G$の次数は$n$であり、$X^{n}$の係数は$p_{G-e}$のそれに等しく$1$である。すなわち$p_G$は次数$n$のモニック多項式である。

任意の正の整数$k$に対し、定理 3.1と帰納法の仮定より$\chi(G;k)=\chi(G-e;k)-\chi(G/e;k)=p_{G-e}(k)-p_{G/e}(k)=p_G(k)$が成り立つ。以上で存在が示された。▨

証明.§D2.12 定義 2.1より、$\chi(G)$は$G$が$k$色による正則な彩色をもつような最小の正の整数$k$である。$G$が$k$色による正則な彩色をもつことと、その個数$\chi(G;k)$が正であることは同値である。ゆえに二つの最小値は一致する。▨

証明.$n$についての帰納法による。

$n=1$のとき、$T$は辺をもたない一頂点のグラフであるから$\chi(T;k)=k=k(k-1)^{0}$である。

$n\ge2$とする。§D2.7 補題 3.2より$T$は次数$1$の頂点$v$をもつ。$v$の唯一の隣接頂点を$u$とし、$T-v$を$T$から頂点$v$と辺$uv$を取り除いて得られるグラフとする。

$T-v$は$n-1$頂点の木である。実際、$T-v$は$T$の部分グラフであるから閉路をもたない。連結性については、$x,y\in V(T)\setminus\{v\}$を結ぶ$T$の道を取ると、$v$はその道の内部の頂点ではない。内部の頂点は道の中で二本の辺に接続するので$T$における次数が$2$以上になり、$\deg_T(v)=1$に反するからである。また$v$は端点でもないので、この道は$T-v$に残る。ゆえに$T-v$は連結であり、§D2.7 定義 3.1より木である。

$T$の$k$色による正則な彩色$c$を、$T-v$への制限$c|_{V\setminus\{v\}}$によって分類する。$c$が$T$の正則な彩色であることは、$c|_{V\setminus\{v\}}$が$T-v$の正則な彩色であり、かつ$c(v)\ne c(u)$が成り立つことと同値である。実際、$T$の辺は$T-v$の辺と辺$uv$からなる。

したがって、$T-v$の正則な彩色$c_0$を一つ固定すると、$c_0$を制限としてもつ$T$の正則な彩色は、$c(v)\in\{1,\dots,k\}\setminus\{c_0(u)\}$の選び方に一対一に対応し、ちょうど$k-1$個である。相異なる$c_0$に対応する彩色の集合は互いに素であり、それらの合併が$T$の正則な彩色の全体であるから、§D2.2 定理 2.1より$\chi(T;k)=(k-1)\,\chi(T-v;k)$が成り立つ。帰納法の仮定より$\chi(T-v;k)=k(k-1)^{n-2}$であるから$\chi(T;k)=(k-1)\cdot k(k-1)^{n-2}=k(k-1)^{n-1}$を得る。▨

証明.$P_n$は連結であり、閉路をもたない。ゆえに§D2.7 定義 3.1より$P_n$は木である。頂点数は$n$であるから、命題 5.1より主張を得る。▨

証明.$n$についての帰納法による。以下、$e=v_1v_2$とする。$C_n-e$は頂点$v_2,v_3,\dots,v_n,v_1$をこの順に結ぶ$n$頂点の道であるから、系 5.2より$\chi(C_n-e;k)=k(k-1)^{n-1}$である。

$n=3$のとき.$C_3/e$を求める。$v_1$と$v_2$を同一視して得られる頂点を$w$とすると、辺$v_2v_3$と$v_3v_1$はいずれも$\{w,v_3\}$を端点の対にもつので一本へまとめられる。ゆえに$C_3/e$は二頂点$w,v_3$と一本の辺からなるグラフであり、これは$2$頂点の木である。命題 5.1より$\chi(C_3/e;k)=k(k-1)$である。定理 3.1より$\chi(C_3;k)=k(k-1)^{2}-k(k-1)=k(k-1)(k-2)$である。一方$(k-1)^{3}+(-1)^{3}(k-1)=(k-1)\bigl((k-1)^{2}-1\bigr)=(k-1)(k^{2}-2k)=k(k-1)(k-2)$であるから、$n=3$で主張が成り立つ。

$n\ge4$のとき.$C_n/e$を求める。$v_1$と$v_2$を同一視して得られる頂点を$w$とすると、辺$v_2v_3$は$\{w,v_3\}$、辺$v_nv_1$は$\{v_n,w\}$を端点の対にもち、$n\ge4$より$v_3\ne v_n$であるから、この二本は平行ではない。残る辺$v_3v_4,\dots,v_{n-1}v_n$は$\pi$で変わらない。ゆえに$C_n/e$は頂点$w,v_3,v_4,\dots,v_n$をこの順に結んで$w$へ戻る長さ$n-1$の閉路であり、$n-1\ge3$であるから$C_{n-1}$と同型である。

定理 3.1と帰納法の仮定より

を得る。▨