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. 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 <math>\lambda_1,\lambda_2,...,\lambda_{n-1}<math> be the non-zero eigenvalues of the admittance matrix of G. Then the number of spanning trees of G is

<math>G=\frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}\,.<math>

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.