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

手順 1：次数行列と隣接行列を作る。
各頂点の次数は、頂点 $1$ が $3$（辺 $\{1,2\},\{1,3\},\{1,4\}$）、頂点 $2$ が $2$、頂点 $3$ が $3$、頂点 $4$ が $2$ である。よって $D=\mathrm{diag}(3,2,3,2)$ である。隣接行列 $A$ は、辺で結ばれた頂点の組の成分が $1$、それ以外が $0$ の行列である。

手順 2：ラプラシアン行列 $L=D-A$ を書く。
$$L=\left(\begin{array}{cccc}3& -1& -1& -1\\ -1& 2& -1& 0\\ -1& -1& 3& -1\\ -1& 0& -1& 2\end{array}\right)$$
（各行の和が $0$ になっていることで検算できる。）

手順 3：1 行目と 1 列目を除いた小行列式を計算する。
行列木定理より、全域木の個数 $\tau (G)$ は $L$ から任意の $i$ 行 $i$ 列を除いた小行列式に等しい。1 行 1 列を除くと
$$\tau (G)=\det \left(\begin{array}{ccc}2& -1& 0\\ -1& 3& -1\\ 0& -1& 2\end{array}\right).$$
1 行目で余因子展開すると
$$2\left|\begin{array}{cc}3& -1\\ -1& 2\end{array}\right|-(-1)\left|\begin{array}{cc}-1& -1\\ 0& 2\end{array}\right|+0=2(6-1)+(-2-0)=10-2=8.$$

検算： $G$ は $K_4$ から辺 $\{2,4\}$ を除いたグラフである。$K_4$ の全域木は $4^2=16$ 個あり、各全域木は $6$ 本の辺のうち $3$ 本を使うので、ある特定の辺を含む全域木は対称性から $16\times \frac{3}{6}=8$ 個。よって辺 $\{2,4\}$ を含まない全域木は $16-8=8$ 個で一致する。

したがって、全域木の個数は $8$ である。

グラフ $G$ は $K_4$ から辺 $\{2,4\}$ を除いたグラフである。次数は $\mathrm{deg}1=3$, $\mathrm{deg}2=2$, $\mathrm{deg}3=3$, $\mathrm{deg}4=2$。

ラプラシアン $L=D-A$ は
$$L=\left(\begin{array}{cccc}3& -1& -1& -1\\ -1& 2& -1& 0\\ -1& -1& 3& -1\\ -1& 0& -1& 2\end{array}\right)$$
行列木定理より、全域木の個数は $L$ の任意の余因子に等しい。第 4 行・第 4 列を除くと
$$M=\left(\begin{array}{ccc}3& -1& -1\\ -1& 2& -1\\ -1& -1& 3\end{array}\right)$$
$\det M=3(2\cdot 3-(-1)(-1))-(-1)((-1)\cdot 3-(-1)(-1))+(-1)((-1)(-1)-2\cdot (-1))$
$=3\cdot 5+(-3-1)-(1+2)=15-4-3=8$。

検算: $K_4$ の全域木は 16 個。各辺は $16\cdot 3/6=8$ 個の全域木に含まれる。よって辺 $\{2,4\}$ を含まない全域木は $16-8=8$ 個で一致する。