One of the oldest results in spectral graph theory is Kirchoff’s matrix-tree theorem, which connects the number of spanning trees of a graph with the spectrum of its Laplacian. Specifically:

Let \(G\) be a connected graph on \(n\) vertices with (nonnormalized) Laplacian \(L\). Let \(L_v\) be a principal submatrix of \(L\) obtained by removing any row and its corresponding column. The number of spanning trees of \(G\) is equal to \(\det (L_v) = \prod_{i=2}^n \lambda_i\).

While studying for my oral exam, I came up with a proof that elides some of the tricky combinatorics by using basic algebraic topology facts. Here goes:

Choose a base vertex \(v\) of the graph, and let \(\partial_v\) be the boundary matrix of \(G\) with the row corresponding to \(v\) removed. Then \(L_v = \partial_v \partial_v^T\). The Cauchy-Binet formula gives a way to compute the determinant of such a product. If we sum over subsets \(S\) of \(n-1\) edges in \(G\), we have

\[\det(L_v) = \sum_{S \in {m \choose {n-1}}} \det( \partial_v|_S) \det((\partial_v|_S)^T) = \sum_{S \in {m \choose {n-1}}} \det(\partial_v|_S)^2.\]

Suppose that \(S\) is a set of \(n-1\) edges that does not form a spanning tree. Then it must contain a cycle, and hence \(\ker ( \partial |\_S )\) is nontrivial, since it is the boundary matrix of a graph with nontrivial \(H_1\). As a result, \(\ker(\partial_v|_S) \neq 0\), and hence \(\det(\partial_v|_S) = 0\). On the other hand, if \(S\) is a spanning tree, \(\ker(\partial|\_S)\) is trivial. Consider the reduced homology of \(G_S\), the graph which has the same vertex set as \(G\) but with only the edges in \(S\), where the distinguished point is \(v\). Since \(G_S\) is a tree, \(\tilde H_0(G_S) = 0\). But this implies that the map \(\partial_v|_S = \pi_{G \setminus v} \circ \partial|_S : \mathbb Z^{n-1} \to \mathbb Z^n \to \mathbb Z^{n-1}\) is an isomorphism, and hence \(\partial_v\mid_S\) is invertible over \(\mathbb Z\), so that \(\det(\partial_v|_S) = \pm 1\). Therefore, \(\det(\partial_v|_S)\det((\partial_v|_S)^T) = 1\) whenever the edges in \(S\) form a spanning tree and \(\det(\partial_v|_S)\det((\partial_v|_S)^T) = 0\) when they do not, and hence the sum from the Cauchy-Binet formula counts the number of spanning trees.

It’s nice when all of the fiddly bits of an argument can be eliminated by appealing to general facts.