Kirchhoff's Theorem¶

Suppose we are given a graph and want to calculate the number of its spanning trees. One of the methods to compute this quantity is Kirchhoff's theorem.

First, we construct an n × n matrix where \(a_{ij}\) is equal to the degree of vertex i when i = j, and otherwise, it is equal to the negative of the number of edges between vertices i and j in the graph. The only point to note is that before constructing the matrix, we must remove all loops from the graph.

Now, we can remove any row and any column we choose and compute the determinant of the resulting matrix (which has lost one row and one column). This determinant equals the number of spanning trees in the graph.