Matrix-Tree Theorem (Spectral Proof)
The number of spanning trees of a graph on vertices is where are the nonzero Laplacian eigenvalues. Equivalently, or any cofactor of .
Proof
Setup. The Laplacian has eigenvalues with eigenvector for .
Step 1: Cofactor formula. We prove equals any cofactor of , say where is obtained by deleting the last row and column.
Cauchy-Binet formula. where is the oriented incidence matrix ( if is the head of edge , if tail, 0 otherwise) and is with the last row deleted. By Cauchy-Binet: where ranges over -element subsets of edges.
Step 2: . The submatrix corresponds to a subgraph with edge set . If is a spanning tree: is the reduced incidence matrix of a tree, which has (proved by induction: a tree has a leaf, and expanding along the leaf's row gives a times a smaller tree incidence determinant). If is not a spanning tree: it contains a cycle or is disconnected, making singular, so .
Step 3: Therefore , summing over spanning trees .
Step 4: Spectral formula. Since has eigenvalues : for all . The cofactor equals ... More directly: by the matrix determinant lemma or direct calculation, any cofactor of equals .
To see this: with orthogonal and . The cofactor matrix is if were invertible. Since , (the projection onto the null space, scaled). Every entry of equals , and each entry is a cofactor.
For : , eigenvalues (mult. 1) and (mult. ). So , recovering Cayley's formula. For : eigenvalues with multiplicities , giving .