Undirected Matrix Tree Theorem

Let be a Graph on vertices whose Laplacian Matrix has Eigenvalues . Then , the number of spanning trees of , is

Proof 1

The number of spanning trees of rooted towards each vertex is the same. Let be the matrix with -th row and column removed. Now by Matrix Tree Theorem:

This is exactly the linear coefficient (in ) of

and the result follows.