Science Fair Project Encyclopedia
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 λ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.
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.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details