Impressive use of the determinant

A spanning tree of a graph G is a connected acyclic subgraph of G that has the same vertex set as G, i.e. it is a tree that covers all the vertices of G. For a given graph G, how many spanning trees are there?

Take the Laplacian of the graph G, remove the last column and the last row of the Laplacian, call this new matrix L^{-}. Now, the amazing result is that the number of spanning trees of G is exactly given by the determinant of L^{-}. This result is known as the Kirchoff’s matrix tree theorem. Its proof is non-obvious (as you might have guessed) and can be found here, together with some other examples of impressive uses of the determinant.

Advertisements