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

頂点を順に塗り、積の法則で数えます。ポイントは、すでに塗った頂点のうち、いま塗る頂点と隣り合うものが何色を使っているかを確かめることです。

手順 1：$a$ を塗る。 まだ何も塗っていないので、$k$ 通りです。

手順 2：$c$ を塗る。 $c$ は $a$ と辺 $ac$ で結ばれているので、$a$ の色以外の $k-1$ 通りです。

手順 3：$b$ を塗る。 $b$ は $a$ とも $c$ とも隣り合っています（辺 $ab$, $bc$）。$a$ と $c$ は異なる色なので、使えない色はちょうど $2$ 色です。よって $k-2$ 通りです。

手順 4：$d$ を塗る。 $d$ も $a$ と $c$ の両方と隣り合っています（辺 $cd$, $da$）。$b$ と $d$ は隣り合っていないので、$b$ の色は気にしなくてよいです。よって $k-2$ 通りです。

どの手順でも、選べる色の数はそれまでの塗り方によらず一定です。したがって積の法則より
$$P_G(k)=k\cdot (k-1)\cdot (k-2)\cdot (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_{C_4}(k)=(k-1{)}^4+(k-1)$ です。
- $G/e$ は $a$ と $c$ を $1$ 点にまとめたグラフです。重なった辺を $1$ 本にすると、$b$―$(ac)$―$d$ という $3$ 頂点の道（木）になるので、$k(k-1{)}^2$ です。

よって
$$P_G(k)=(k-1{)}^4+(k-1)-k(k-1{)}^2=(k-1)\{(k-1{)}^3+1-k(k-1)\}.$$
中かっこの中を展開すると
$$k^3-3k^2+3k-1+1-k^2+k=k^3-4k^2+4k=k(k-2{)}^2$$
です。したがって $P_G(k)=k(k-1)(k-2{)}^2$ となり、上の結果と一致します。

（例：$k=3$ のとき $P_G(3)=3\cdot 2\cdot 1\cdot 1=6$ です。）

$G$ は 4 頂点で、辺 $ab,bc,cd,da,ac$ を持つ。対角線 $ac$ を共有する 2 つの三角形 $abc$ と $acd$ を貼り合わせた形である。

数え上げ：まず $a,c$ を塗る。$ac$ は辺なので $k(k-1)$ 通り。
$b$ は $a,c$ の両方と隣り合い、$a,c$ は異なる色なので、$b$ の色は $k-2$ 通り。
$d$ も同様に $a,c$ と隣り合うので $k-2$ 通り。$b$ と $d$ は隣り合わないので独立に選べる。

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

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

検算：削除・縮約の公式を使う。$P_G=P_{G-ac}-P_{G/ac}$。$G-ac$ は 4 サイクルで $P=(k-1{)}^4+(k-1)$。$G/ac$ は頂点 $a=c$ に $b,d$ が結ばれた三角形ではなく、辺 $(ac)b$, $(ac)d$ の道（2 辺の道）なので $P=k(k-1{)}^2$。

$(k-1{)}^4+(k-1)=k^4-4k^3+6k^2-4k+1+k-1=k^4-4k^3+6k^2-3k$。
$k(k-1{)}^2=k^3-2k^2+k$。
差は $k^4-5k^3+8k^2-4k$ となり一致する。

また $k=2$ では $0$（三角形を含むので 2 色では不可能）、$k=3$ では $3\cdot 2\cdot 1=6$ となり、妥当である。