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

手順 1：次数を求める。 各頂点に接続する辺を数えると、
$$\mathrm{deg}1=3,\mathrm{deg}2=2,\mathrm{deg}3=3,\mathrm{deg}4=2$$
である（握手補題より合計 $10=2\times 5$ で、辺数 $5$ と合う）。

手順 2：ラプラシアン行列を作る。 対角成分には次数を、$i\ne j$ の成分には「$\{i,j\}$ が辺なら $-1$、そうでなければ $0$」を入れる。辺 $\{2,4\}$ はないので、$(2,4)$ 成分と $(4,2)$ 成分は $0$ である。
$$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：行列木定理を使う。 行列木定理より、全域木の個数 $\tau (G)$ は $L$ から 1 行目と 1 列目を除いた小行列の行列式に等しい。
$$\tau (G)=\det \left(\begin{array}{ccc}2& -1& 0\\ -1& 3& -1\\ 0& -1& 2\end{array}\right)$$

手順 4：行列式を計算する。 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$ の全域木の個数は $8$ である。

（確認：$G$ は $K_4$ から辺 $\{2,4\}$ を除いたグラフである。$K_4$ の全域木は $4^2=16$ 個あり、対称性からどの辺も $16\times 3÷6=8$ 個の全域木に含まれるので、$16-8=8$ となり一致する。）

次数は、頂点1: 辺{1,2},{4,1},{1,3}で3、頂点2: 2、頂点3: {2,3},{3,4},{1,3}で3、頂点4: 2。

ラプラシアン行列は
$$L=\left(\begin{array}{cccc}3& -1& -1& -1\\ -1& 2& -1& 0\\ -1& -1& 3& -1\\ -1& 0& -1& 2\end{array}\right)$$
行列木定理より、任意の1つの行と列(ここでは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$。

検算：$G$ は $K_4$ から辺{2,4}を除いたグラフである。$K_4$ の全域木は16個で、辺{2,4}を含むものは $16\cdot 3/6=8$ 個なので、含まないものは $16-8=8$ 個。一致する。