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

行列木定理. 連結グラフ $G$（頂点数 $n$）のラプラシアン行列 $L(G)=D-A$ の固有値を $0={\mu }_1\le {\mu }_2\le \cdots \le {\mu }_n$ とすると、全域木の個数は
$$\tau (G)=\frac{1}{n}{\mu }_2{\mu }_3\cdots {\mu }_n.$$

固有値の計算. 取り除いた辺からなるグラフを $H$（頂点集合 $\{1,\dots ,7\}$、辺 $\{1,2\},\{3,4\},\{5,6\}$）とすると
$$L(G)=L(K_7)-L(H)=7I-J-L(H)$$
（$J$ は全成分 $1$ の行列）。

$L(H)$ は $3$ 個の $K_2$ のラプラシアン $\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$（固有値 $0,2$）と、孤立点 $7$ の $1\times 1$ 零行列のブロック対角なので、固有値は $0$（重複度 $4$）と $2$（重複度 $3$）。$L(H)$ は実対称で $L(H)1=0$ なので、$1=(1,\dots ,1{)}^{\mathsf{T}}$ を含む直交固有ベクトル基底がとれる。
- $1$ に対して $L(G)1=71-71-0=0$。
- $1$ に直交する固有ベクトル $v$（$L(H)v=\mu v$）では $Jv=0$ なので $L(G)v=(7-\mu )v$。

$1$ に直交する固有ベクトルの固有値 $\mu$ は、$0$ が $4-1=3$ 個、$2$ が $3$ 個。よって $L(G)$ の $0$ 以外の固有値は $7$（重複度 $3$）と $5$（重複度 $3$）。

全域木の個数.
$$\tau (G)=\frac{1}{7}\cdot 7^3\cdot 5^3=49\cdot 125=6125.$$

（検算: 一般に $K_n$ から互いに素な $k$ 本の辺を除くと $\tau =n^{n-2}{\left(1-\frac{2}{n}\right)}^k$。$n=7$, $k=3$ で $7^5\cdot {\left(\frac{5}{7}\right)}^3=7^2\cdot 5^3=6125$。）

答えは $6125$。

$G$ の補グラフは 3 本の独立な辺と孤立点 1 個からなり、そのラプラシアンの固有値は $0$（4 個）と $2$（3 個）。$n=7$ のとき $\tau (G)=\frac{1}{n^2}{\prod }_i(n-{\mu }_i)$（${\mu }_i$ は補グラフのラプラシアン固有値すべて）なので $\tau (G)=\frac{7^4\cdot 5^3}{7^2}=7^2\cdot 125=6125$。検算: $K_7$ の全域木は $7^5=16807$ 個で、辺を 1 本除くと $7^5\cdot (1-\frac{2}{7})=12005$ となり、この公式（$K_n-e$ は $n^{n-2}(1-2/n)$）と整合している。