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] An Example Using the Matrix-Tree Theorem
We first construct a matrix Q for the graph G such that:
- for i
j
- if vertex i is adjacent to vertex j in G, qi,j equals -1
- otherwise, qi,j equals 0
- if vertex i is adjacent to vertex j in G, qi,j equals -1
- for i = j, qi,j (that is, qi,i) equals the degree of vertex i in G
Using the kite in this example (see image at right),
We now construct a matrix Q* by deleting any row s and any column t (s and t not necessarily distinct) from Q. For this example, we will delete row 1 and column 1 to obtain
Finally, we take the determinant of Q* to obtain t(G), which is 8 in this example.
[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.
