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

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise).

For a given connected graph G with n labeled vertices, let λ₁, λ₂, ..., λ_n−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is

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

Equivalently the number of spanning trees is equal to the absolute value of any cofactor of the Laplacian matrix of G.

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 first construct the Laplacian matrix Q for the example kite graph G (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). t(G) is thus the (1,1) cofactor of Q. In this example t(G) is 8.

Proof outline

First notice that the Laplacian has the property that the sum of its entries across any row and any column is 0. Thus we can transform any minor into any other minor by adding rows and columns, switching them, and multiplying a row or a column by −1. Thus the cofactors are the same up to sign, and it can be verified that, in fact, they have the same sign.

We proceed to show that the determinant of the minor M₁₁ counts the number of spanning trees. Let n be the number of vertices of the graph, and m the number of its edges. The incidence matrix E is an n-by-m matrix. Suppose that (i, j) is the kth edge of the graph, and that i < j. Then E_ik = 1, E_jk = −1, and all other entries in column k are 0. For the preceding example (with n = 4 and m = 5):

$E = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ -1 & 0 & 0 & 1 & 0 \\ 0 & -1 & 0 & -1 & 1 \\ 0 & 0 & -1 & 0 & -1 \\ \end{bmatrix}.$

Recall that the Laplacian L can be factored into the product of the incidence matrix and its transpose, i.e., L = EE^T. Furthermore, let F be the matrix E with its first row deleted, so that FF^T = M₁₁.

Now the Cauchy-Binet formula allows us to write

$\det(M_{11}) = \sum_S \det(F_S)\det(F^T_S) = \sum_S \det(F_S)^2$

where S ranges across subsets of [m] \ {1} of size n − 1, and F_S denotes the (n − 1)-by-(n − 1) matrix whose columns are those of F with index in S. Then every S specifies n − 1 edges of the original graph, and it can be shown that those edges induce a spanning tree iff the determinant of F_S is +1 or −1, and that they do not induce a spanning tree iff the determinant is 0. This completes the proof.

Particular cases and generalizations

Cayley's formula

Cayley's formula follows from Kirchhoff's theorem as a special case, since 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.

Alternatively, note that as Cayley's formula counts the number of distinct labeled trees of a complete graph K_n we need to compute any cofactor of the Laplacian matrix of K_n. The Laplacian matrix in this case is

$\begin{bmatrix} n-1 & -1 & \cdots & -1 \\ -1 & n-1 & \cdots & -1 \\ \vdots & & \ddots & \vdots \\ -1 & -1 & \cdots & n-1 \\ \end{bmatrix}.$

It can be easily verified that any cofactor of the above matrix is nⁿ⁻² which is Cayley's formula.

Kirchhoff's theorem for multigraphs

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, q_i,j equals −m, where m is the number of edges between i and j;
• when counting the degree of a vertex, all loops are excluded.

Explicit enumeration of spanning trees

Kirchhoff's theorem can be strengthened by 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 an indeterminant and let the (i,j)-th entry of the modified Laplacian matrix be the sum over the indeterminants corresponding to edges between the i-th and j-th vertices when i does not equal j, and the negative sum over all indeterminants corresponding to edges emanating from the i-th vertex when i equals j.

The determinant above is then a homogeneous polynomial (the Kirchhoff polynomial) in the indeterminants corresponding to the edges of the graph. After collecting terms and performing all possible cancellations, each monomial in the resulting expression represents a spanning tree consisting of the edges corresponding to the indeterminants appearing in that monomial. In this way, one can obtain explicit enumeration of all the spanning trees of the graph simply by computing the determinant.

See also

• Prufer sequences
• Minimum spanning tree
• List of topics related to trees

References

• John M. Harris, Jeffry L. Hirst, Michael J. Mossinghoff (2008). Combinatorics and Graph Theory. Undergraduate Texts in Mathematics (2nd ed.). Springer. 
• Tutte, W. T. (2001), Graph Theory, Cambridge University Press, p. 138, ISBN 978-0-521-79489-3 

External links

• A proof of Kirchoff's theorem
• A discussion on the theorem and similar results