Kirchhoff's theorem
In the mathematical field of graph theory Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time as the determinant of a matrix derived from the graph. It is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.
Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise).
For a given connected graph G with n labeled vertices, let λ1, λ2, ..., λn−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is
Equivalently the number of spanning trees is equal to any cofactor of the Laplacian matrix of G.
First, construct the Laplacian matrix Q for the example diamond graph G (see image at right):
Next, construct a matrix Q* by deleting any row and any column from Q. For example, deleting row 1 and column 1 yields
Finally, take the determinant of Q* to obtain t(G), which is 8 for the diamond graph. (Notice t(G) is the (1,1)-cofactor of Q in this example.)
...
Wikipedia