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

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

手順 2：ラプラシアン行列を作る。 対角成分は次数、$(i,j)$ 成分（$i\ne j$）は $i,j$ が隣接していれば $-1$、隣接していなければ $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)$$

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

確認： 辺は 5 本あり、全域木は 3 本の辺からなるので、3 本の選び方は ${}_5{\mathrm{C}}_3=10$ 通り。このうち閉路（三角形）になるのは $\{1,2\},\{2,3\},\{1,3\}$ と $\{1,3\},\{3,4\},\{4,1\}$ の 2 通りで、残りはすべて全域木になる。よって $10-2=8$ となり一致する。

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

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

ラプラシアン行列は
L = [[3,-1,-1,-1],[-1,2,-1,0],[-1,-1,3,-1],[-1,0,-1,2]]。

行列木定理より、任意の1行1列を除いた小行列式が全域木の個数である。第4行・第4列を除くと
M = [[3,-1,-1],[-1,2,-1],[-1,-1,3]]。

det M = 3(2·3-(-1)(-1)) - (-1)((-1)·3-(-1)(-1)) + (-1)((-1)(-1)-2·(-1))
= 3·5 + 1·(-3-1) - (1+2)
= 15 - 4 - 3 = 8。

検算: G は K4 から辺{2,4}を除いたグラフである。K4 の全域木は 16 個で、各辺は 16·3/6=8 個の全域木に含まれる。辺{2,4}を含まない全域木は 16-8=8 個。よって一致する。