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

行列木定理（キルヒホッフの定理）より、$n$ 頂点の連結グラフの全域木の個数は、ラプラシアン行列 $L$ の 0 でない固有値 ${\mu }_1,\dots ,{\mu }_{n-1}$ を用いて
$$\tau (G)=\frac{1}{n}{\mu }_1{\mu }_2\cdots {\mu }_{n-1}$$
で与えられる。

ラプラシアン行列. $G$ の各頂点の次数は $7-1=6$ である。$J$ を全成分が 1 の $8\times 8$ 行列、$M$ を取り除いた 4 本の辺（完全マッチング）の隣接行列とすると、$G$ の隣接行列は $J-I-M$ なので
$$L=6I-(J-I-M)=7I-J+M.$$

固有値. $M$ は対称行列で、次の 8 本の互いに直交するベクトルを固有ベクトルにもつ。
- 各組 $\{1,2\},\{3,4\},\{5,6\},\{7,8\}$ の中で同じ値をとるベクトル（4 次元の空間）: $M$ の固有値 $1$。
- 各組の中で符号が反対の値をとるベクトル（4 次元の空間）: $M$ の固有値 $-1$。

これらに対して $L$ の作用を調べる。
- 全成分 1 のベクトル $1$（組の中で同じ値）: $J1=81$, $M1=1$ より $L1=(7-8+1)1=0$。
- 組の中で同じ値をとり、$1$ と直交するベクトル（3 次元）: $J$ で 0 に移るので、固有値 $7-0+1=8$。
- 組の中で符号が反対のベクトル（4 次元）: 成分の和が 0 なので $J$ で 0 に移り、固有値 $7-0-1=6$。

よって $L$ の固有値は $0$（1 重）, $8$（3 重）, $6$（4 重）である。

全域木の個数.
$$\tau (G)=\frac{1}{8}\cdot 8^3\cdot 6^4=64\cdot 1296=82944.$$

確認: 同じ方法を $K_4$ から完全マッチングを除いたグラフ（4 頂点の閉路 $C_4$）に適用すると、固有値は $0,4,2,2$ で $\tau =\frac{1}{4}\cdot 4\cdot 2^2=4$ となり、$C_4$ の全域木が 4 個であることと一致する。

$G$ は 4 組の非隣接対をもつ完全 4 部グラフ $K_{2,2,2,2}$ で、6 正則。隣接行列の固有値は $6$（重複度 1）、$0$（重複度 4）、$-2$（重複度 3）である（$A=J-I-P$、$P$ は取り除いた完全マッチングの隣接行列で、$P$ の固有値は $1$（重複度 4）、$-1$（重複度 4））。実際 $J$ と $P$ は可換で、全 1 ベクトルでは $A=8-1-1=6$、$P$ の固有値 $1$ の固有空間のうち全 1 に直交する部分では $A=-1-1=-2$（重複度 3）、$P$ の固有値 $-1$ の固有空間（重複度 4）では $A=-1+1=0$。ラプラシアン固有値は $6-\lambda$ より $0,6(\times 4),8(\times 3)$。行列木定理（固有値版）より全域木の個数は $\frac{1}{8}\cdot 6^4\cdot 8^3=\frac{1296\cdot 512}{8}=82944$。検算: 固有値の和 $24+24=48$ はトレース $=\sum \mathrm{deg}=48$ と一致。