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. It is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

Kirchhoff's Theorem

Given a connected graph G with n vertices, let λ₁,λ₂,...,λ_{n - 1} be the non-zero eigenvalues of the admittance matrix of G. Then the number of spanning trees of G is

In other words the number of spanning trees is equal to any cofactor of the admittance matrix of G.

Notes

Seeing that Cayley's formula follows from Kirchoff's theorem as a special case is easy: every vector with 1 in one place, -1 in another place, and 0 elsewhere is an eigenvector of the admittance matrix of the complete graph, with the corresponding eigenvalue being n.