### 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.