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 Laplacian matrix of G. Then the number of spanning trees of G is

t(G)=\frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}\,.

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

[edit] An example using the matrix-tree theorem

We can compute the number of labeled spanning trees of this kite with the Matrix-Tree Theorem.
We can compute the number of labeled spanning trees of this kite with the Matrix-Tree Theorem.

We first construct a matrix Q for the graph G such that:

  • for i \neq j
    • if vertex i is adjacent to vertex j in G, qi,j equals -1
    • otherwise, qi,j equals 0
  • 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),

Q = \left[\begin{array}{rrrr} 3 & -1 & -1 & -1 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -1 & 0 & -1 & 2 \end{array}\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

Q^\ast = \left[\begin{array}{rrr} 2 & -1 & 0 \\ -1 & 3 & -1 \\ 0 & -1 & 2 \end{array}\right]

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 Laplacian 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.

Kirchhoff's theorem holds for multigraphs as well; the matrix Q is modified as follows:

  • if vertex i is adjacent to vertex j in G, qi,j equals -m, where m is the number of edges between i and j
  • when counting the degree of a vertex, you exclude all loops.

Kirchhoff's formula can be strengthened quite considerably by slightly altering the definition of the Laplacian matrix: Rather than merely counting edges emanating from each vertex or connecting a pair of vertices, label each edge with a variable or indeterminant and let the (i,j)th entry of the modified Laplacian matrix be the sum over the indeterminants corresponding to edges between the ith and jth vertex when i does not equal j and the negative sum over all indeterminants corresponding to edges emanating from the ith vertex when i equals j. The determinant above is then a homogeneous polynomial in the indeterminants corresponding to the edges of the graph. After collecting terms and performing all possible cancellations, each monomial appearing in this determinant corresponds to a spanning tree of the graph consisting of exactly those edges corresponding to the indeterminants appearing in that monomial. In this way, one can obtain explicit knowledge of all the spanning trees of a graph simply by computing a determinant.