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 from the determinant of a submatrix of the graph's Laplacian matrix; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem 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, which is equal to the difference between the graph's degree matrix (the diagonal matrix of vertex degrees) 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 λ₁, λ₂, ..., λ_n−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is

${\displaystyle t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}\,.}$

An English translation of Kirchhoff's original 1847 paper was made by J. B. O'Toole and published in 1958.^[1]