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

方針：頂点を順に塗り、積の法則を使う。

$G$ では $a$ と $c$ が辺 $ac$ で結ばれ、$b$ と $d$ はどちらも $a$ と $c$ の両方に隣接している（$b$ と $d$ の間に辺はない）。そこで $a\to c\to b\to d$ の順に塗る。

• $a$ の色：制約がないので $k$ 通り。
• $c$ の色：$a$ と隣接しているので、$a$ の色以外の $k-1$ 通り。
• $b$ の色：$a$ と $c$ の両方に隣接しており、$a$ と $c$ は異なる色なので、その 2 色以外の $k-2$ 通り。
• $d$ の色：同様に $a$ と $c$ の両方に隣接しているので $k-2$ 通り。$b$ とは隣接していないので、$b$ と同じ色でもよい。

どの段階でも選べる色の数は、それまでの塗り方によらず一定なので、積の法則より
$$P_G(k)=k(k-1)(k-2)(k-2)=k(k-1)(k-2{)}^2.$$

検算（削除縮約公式）： 辺 $e=ac$ について $P_G(k)=P_{G-e}(k)-P_{G/e}(k)$。$G-e$ は長さ 4 の閉路 $C_4$ なので $P_{G-e}(k)=(k-1{)}^4+(k-1)$。$G/e$ は $a,c$ を 1 点 $x$ にまとめたグラフで、辺は $xb,xd$ のみ（頂点 3 個の木）なので $P_{G/e}(k)=k(k-1{)}^2$。よって
$$P_G(k)=(k-1)\{(k-1{)}^3+1-k(k-1)\}=(k-1)(k^3-4k^2+4k)=k(k-1)(k-2{)}^2$$
となり、一致する。

$G$ は 4 頂点で、辺 $ab,bc,cd,da,ac$ をもつ。これは 4 点の閉路 $a\text{-}b\text{-}c\text{-}d\text{-}a$ に対角線 $ac$ を加えたグラフで、$K_4$ から辺 $bd$ を除いたものである。

直接数える。まず $a,c$ を塗る。$ac$ は辺なので、$a$ は $k$ 通り、$c$ は $k-1$ 通り。
次に $b$ は $a,c$ の両方と隣接するので、$a,c$ と異なる色を選び $k-2$ 通り。$d$ も同様に $a,c$ の両方と隣接するので $k-2$ 通り。$b$ と $d$ は隣接しないので独立に選べる。

よって $P_G(k)=k(k-1)(k-2{)}^2$。

検算：削除・縮約で確かめる。辺 $bd$ を加えたグラフは $K_4$ で $P_{K_4}(k)=k(k-1)(k-2)(k-3)$。辺 $bd$ を縮約したグラフは三角形 $a,c,bd$ で $k(k-1)(k-2)$。$P_G=P_{G+bd}+P_{G/bd}=k(k-1)(k-2)(k-3)+k(k-1)(k-2)=k(k-1)(k-2)(k-2)$。一致する。

また $k=2$ のとき 0（三角形を含む）、$k=3$ のとき $3\cdot 2\cdot 1=6$ で妥当。