Kirchhoff's matrix tree theorem

Remarks

Orient each edge and let $B$ be the $n \times m$ incidence matrix, with entries $+1$ and $-1$ at the head and tail of each edge; then $L = B B^T$. Delete row $i$ of $B$ to get $B_i$, so that $L_i = B_i B_i^T$. By the Cauchy–Binet formula, $\det L_i$ is the sum of $(\det N)^2$ over the $(n-1) \times (n-1)$ submatrices $N$ of $B_i$. Such a minor is $\pm 1$ if its $n - 1$ edges form a spanning tree and $0$ otherwise, which gives the count.

Example: for the triangle $K_3$, every vertex has degree $2$ and $$L_3 = \begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}, \qquad \det L_3 = 3,$$ which matches the $3$ spanning trees obtained by removing one edge. For the complete graph $K_n$ the theorem gives $n^{n-2}$, which is Cayley's formula. If $G$ is not connected, both sides are $0$.

Going deeper

For a student

An equivalent form uses the eigenvalues $0 = \mu_1 \le \mu_2 \le \dots \le \mu_n$ of $L$: the number of spanning trees is $\frac{1}{n} \mu_2 \cdots \mu_n$. This links spectral graph theory to enumeration. The theorem goes back to Kirchhoff's study of electrical networks. It has a weighted version, where each edge carries a variable and the determinant sums the weights of the spanning trees, and a version for directed graphs that counts arborescences.