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.