Kirchoff's matrix tree theorem

Statement

The number of spanning trees of a graph $G$ (yes multiedges, no self-loops) is the determinant of $\tilde{L}$ , the reduced Laplacian matrix (for any $i$ ).

Furthermore, the rank of $L$ (the Laplacian (Kirchoff) matrix) is $n - c$ where $n$ is the number of vertices and $c$ is the number of connected components.

Another formulation: if the eigenvalues of $\tilde{L}$ is $λ_{1}, \dots, λ_{n}$ with $λ_{n} = 0$ , then the number of spanning trees of $G$ is equal to

\frac{1}{n} λ_{1} \dots λ_{n - 1}

Proof

Direct the edges of $G$ arbitrarily. First, we collect some lemmas:

Lemma: $L = B \cdot B^{T}$ for any fixed orientation of the edges. (where $B$ is the oriented incidence matrix)
The $(i, j)$ entry of $B \cdot B^{T}$ is the dot product of the $i$ th and $j$ th rows of $B$ .
If $i = j$ , this gives us the number of edges that are incident to $i$ .
If $i \neq j$ , this gives us the negation of the number of edges connecting $i$ and $j$ .
We note that this is exactly the $(i, j)$ entry of $L$ .

Lemma: $\tilde{L} = \tilde{B} \cdot {\tilde{B}}^{T}$ where $\tilde{B}$ is $B$ with the $i$ th row and column removed.
Follows from the above.

Applying Cauchy-Binet formula to the above equation, we get

det (\tilde{L}) = det (\tilde{B} {\tilde{B}}^{T}) = \sum_{| S | = n - 1} (det {\tilde{B}}_{S})^{2}

Key Lemma: $det {\tilde{B}}_{S} = \pm 1$ if $S$ is the set of edges of a spanning tree. 0 otherwise.
Suppose $S$ does not form a spanning tree. Since it has $n - 1$ edges, it has to have a cycle. Then, the sum of all the corresponding columns of the cycle in ${\tilde{B}}_{S}$ will be 0, which yields a linear dependence. Thus, the determinant is 0.
Suppose $S = T$ forms a spanning tree. As long as the tree has at least 2 vertices, it will have at least 2 leaves. These leaves correspond to a row in ${\tilde{B}}_{T}$ that only has 1 nonzero entry. We note then that $det {\tilde{B}}_{T} = \pm det {\tilde{B}}_{T^{'}}$ where $T^{'}$ is $T$ without the leaf, still a tree. We may continue doing this until there are no more edges left, and we see that the determinant will always be $\pm 1$ .
It turns out in general that the oriented incidence matrix of a graph is totally unimodal

With this lemma, we conclude the theorem.

The equivalent statement that it is the product of the eigenvalues comes from looking at the two ways to find the linear term of the characteristic polynomial of $L$

The characteristic polynomial will look like $λ_{n} (x - λ_{1}) \dots (x - λ_{n - 1})$ and so the coefficient of the linear term will be $(- 1)^{n - 1} \prod_{i = 1}^{n - 1} λ_{i}$
Note that the coefficient of $λ^{1}$ in $det (λ I - L)$ is also the sum of the $(n - 1) \times (n - 1)$ minors, ie. $(- 1)^{n - 1} \sum_{i = 1}^{n} det ({\tilde{L}}_{i})$ which gives us $n$ times the number of spanning trees

Combining these two yields that

\prod_{i = 1}^{n - 1} λ_{i} = # spanning trees of G