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, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.
Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph, which 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 λ1, λ2, ..., λn−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is
An English translation of Kirchhoff's original 1847 paper was made by J. B. O'Toole and published in 1958.
An example using the matrix-tree theorem
First, construct the Laplacian matrix Q for the example diamond graph G (see image on the right):
Next, construct a matrix Q* by deleting any row and any column from Q. For example, deleting row 1 and column 1 yields
Finally, take the determinant of Q* to obtain t(G), which is 8 for the diamond graph. (Notice t(G) is the (1,1)-cofactor of Q in this example.)
Proof outline
(The proof below is based on the Cauchy–Binet formula. An elementary induction argument for Kirchhoff's theorem can be found on page 654 of Moore (2011).)
First notice that the Laplacian matrix 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 M11 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, which may be defined as follows: suppose that (i, j) is the kth edge of the graph, and that i < j. Then Eik = 1, Ejk = −1, and all other entries in column k are 0 (see oriented incidence matrix for understanding this modified incidence matrix E). For the preceding example (with n = 4 and m = 5):
Recall that the Laplacian L can be factored into the product of the incidence matrix and its transpose, i.e., L = EET. Furthermore, let F be the matrix E with its first row deleted, so that FFT = M11.
Now the Cauchy–Binet formula allows us to write
where S ranges across subsets of [m] of size n − 1, and FS 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 if and only if the determinant of FS is +1 or −1, and that they do not induce a spanning tree if and only if 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 Kn we need to compute any cofactor of the Laplacian matrix of Kn. The Laplacian matrix in this case is
Any cofactor of the above matrix is nn−2, 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: The entry qi,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. Cayley's formula for a complete multigraph is by same methods produced above, since a simple graph is a multigraph with m = 1.