24 Apr 2026

The engineers among the readers may recall Kirchhoff's two circuit laws, which state that the current and voltage is preserved when transitioning a node, i.e., that the sum of the incoming such quantities equals the sum of the outgoing ones. There is, however, another result also attributed to Kirchhoff which has little to no relation with the previous one: Kirchhoff's theorem for spanning trees.

First, it is worth remembering a few concepts about graphs, namely spanning trees themselves and the Laplacian matrix. A tree is a connected, undirected graph with no cycles, and given any connected graph $G$, we can remove some of its edges so that it becomes a tree; the resulting object is called a spanning tree of $G$:

A connected graph.
Its spanning tree.

The second concept comes from algebra; the fundamental bridge that joins the two disciplines together is the adjacency matrix of a graph, which has ones at the positions $(i, j)$ when $v_i$ and $v_j$ are connected by an edge. Since we are dealing today with undirected graphs, their adjacency matrices are symmetric and therefore orthogonally diagonalizable by the spectral theorem, but we will not go down this rabbit hole this time. Instead, we define the Laplacian matrix of a graph as $$ L = D - A, $$ where $D$ is the diagonal matrix containing the degrees of the vertices as entries, and $A$ is the aforementioned adjacency matrix. This funny name comes from the property that interpreting column vectors as functions $f: V \longrightarrow \mathbf R$ yields $$ Lf_i = \delta(i)f(i) - \sum_{j \sim i} f(j) = \sum_{j \sim i} (f(i) - f(j)), $$ which resembles the Laplacian operator in a discrete fashion; again, let's stick to the point, I may write a whole post on the numerous applications of the Laplacian matrix one day (Fiedler eigenvalues/eigenvectors, spectral drawing, and even the heat equation appears there too!).

Now we are in the position to know that Kirchhoff's theorem states the following:

The number of spanning trees of a graph $G$ is given by any of the cofactors of its Laplacian matrix.

This is interesting because the theorem holds for any of the cofactors, not just one, and also because it gives an explicit procedure for computing the number of spanning trees. A not-so-boring proof by induction is given in Moore and Mertens' The Nature of Computation, so I will not go over it here.

Finally, referring back to electric circuits, an analog to Laplacian matrices may be used to study alternating current circuits, by setting the positions $(i, j)$ to be the negative of the reciprocal of the impedance between them. They are complex matrices, but they are symmetric instead of Hermitian, which is somewhat disappointing. As far as I know, however, Kirchhoff's theorem still does not have any relation with Kirchhoff's laws.