A spanning tree of a graph is a connected acyclic subgraph of that has the same vertex set as , i.e. it is a tree that covers all the vertices of . For a given graph , how many spanning trees are there?
Take the Laplacian of the graph , remove the last column and the last row of the Laplacian, call this new matrix . Now, the amazing result is that the number of spanning trees of is exactly given by the determinant of . 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.