Matrix Tree Theorem

Let be a Weighted Graph.
Let be its Laplacian Matrix.
Let be derived from by removing the -th row and -th column.
Consider all the spanning trees of rooted towards .
The sum of all of their weights equals .

Proof 1

By induction on the number of edges with nonzero weight .
The case is trivial.
Consider the edge .
Let be the combined weight of trees directed towards .
Then

Note that the Adjacency Matrix of is formed by:

1. removing row and column
2. replacing with
3. replacing with
   Matrix is formed from in the same way, from where the result follows.

Proof 2

Fix a permutation of .
Set and .
Consider a term in the expansion of :

Then we note that:

where we sum over all , so define:

Suppose that either has a cycle in or has a cycle in .
Take the smallest vertex belonging to one of these cycles.
Now define and by swapping this cycle between and
(i.e. if the cycle was in , put it into and vice versa)
Note that and , so we made a good pairing.
Also if this cycle was of odd length, then , while
and if the cycle was of even length, then the opposite holds.
Either way, the sign of changes.
But the actual product doesn’t i.e:

Thus in the final sum, all of these pairings will cancel eachother out.
The only unpaired terms are when and has no cycles.
We conclude that

where we sum over all with no cycles.
But these are exactly the spanning trees of rooted towards .

Proof 3

Using Exterior Algebra, we find:

where .
Now we expand to find

summing over all .
If contains a cycle, then are not all linearly independent
(e.g. , , ).
So the product is non zero only if contains no cycles
(i.e. is a tree rooted towards ).
Also note that for any such :

which completes the proof.
The last remark can be seen as follows:
In -th bracket , we can choose or .
Suppose for some we choose .
Then in we cannot choose because
Thus we always need to choose .
But eventually, and so these terms always vanish.
The only one left is choosing in every bracket.