離散数学・組合せ論の問題

方法 1：頂点を順に塗る（積の法則）

頂点を $a,c,b,d$ の順に塗る。

• $a$：制約がないので $k$ 通り。
• $c$：$a$ と辺 $ac$ で結ばれているので、$a$ の色以外の $k-1$ 通り。
• $b$：$a$ と $c$ の両方と結ばれている（辺 $ab,bc$）。$a$ と $c$ は異なる色なので、使えない色はちょうど $2$ 色であり、$k-2$ 通り。
• $d$：同様に $a$ と $c$ の両方と結ばれている（辺 $da,cd$）。$b$ と $d$ は結ばれていないので $b$ の色は関係しない。よって $k-2$ 通り。

各段階の通り数は、それまでの塗り方によらず一定である。したがって積の法則より
$$P_G(k)=k(k-1)(k-2)(k-2)=k(k-1)(k-2{)}^2.$$

方法 2：削除縮約公式による確認

$e=ac$ として $P_G(k)=P_{G-e}(k)-P_{G/e}(k)$ を使う。

• $G-e$ は長さ $4$ の閉路 $C_4$ である。閉路の公式 $(k-1{)}^n+(-1{)}^n(k-1)$ で $n=4$ とすると、$P_{G-e}(k)=(k-1{)}^4+(k-1)$。
• $G/e$ は $a$ と $c$ を 1 つの頂点 $w$ にまとめたグラフである。辺 $ab$ と $cb$ はどちらも $wb$ になり、辺 $ad$ と $cd$ はどちらも $wd$ になる。重なった辺は 1 本とみなしてよく、辺は $wb,wd$ の 2 本となる。これは頂点数 $3$ の木なので、木の公式 $k(k-1{)}^{n-1}$ より $P_{G/e}(k)=k(k-1{)}^2$。

よって
$$\begin{array}{rl}{P}_G(k)& =(k-1{)}^4+(k-1)-k(k-1{)}^2\\ & =(k-1)\{(k-1{)}^3+1-k(k-1)\}\\ & =(k-1)(k^3-3k^2+3k-1+1-k^2+k)\\ & =(k-1)(k^3-4k^2+4k)\\ & =k(k-1)(k-2{)}^2.\end{array}$$

2 つの方法の結果は一致する。よって $P_G(k)=k(k-1)(k-2{)}^2$ である。

$G$ は $K_4$ から辺 $bd$ を除いたグラフである。

【方法1】$a,c$ は隣接しているので、$a$ の色の選び方は $k$ 通り、$c$ の色は $k-1$ 通り。
$b$ は $a,c$ の両方と隣接しているので $k-2$ 通り。
$d$ も $a,c$ の両方と隣接していて、$b$ とは隣接していないので $k-2$ 通り。
よって $P_G(k)=k(k-1)(k-2{)}^2$。

【方法2（検算）】削除・縮約の公式を使う。$P_G=P_{G+bd}-...$ ではなく、$P_G=P_{G+bd}+P_{G/bd}$ とする。ここで $G+bd=K_4$ なので $P=k(k-1)(k-2)(k-3)$ である。$b$ と $d$ を同一視した $G/bd$ は三角形 $a,c,(bd)$ であり、$P=k(k-1)(k-2)$ である。
合計は $k(k-1)(k-2)[(k-3)+1]=k(k-1)(k-2{)}^2$。方法1と一致する。

【確認】$k=2$ では 0 となる。三角形を含むので 2 色では塗れず正しい。$k=3$ では $3\cdot 2\cdot 1=6$ 通りである。$a,c,b$ の色は 3! 通りで決まり、$d$ は $b$ と同じ色に決まるので、6 通りで一致する。

展開すると $k(k-1)(k^2-4k+4)=k^4-5k^3+8k^2-4k$。