Kirchhoff's theorem
From Wikipedia, the free encyclopedia
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.
[edit] Kirchhoff's theorem
Given a connected graph G with n vertices, let λ1,λ2,...,λ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.
[edit] Notes
Seeing that Cayley's formula follows from Kirchhoff'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. These vectors together span a space of dimension n-1, so there are no other non-zero eigenvalues.
