Matrix-Tree Theorem

From Electrical Circuits to Combinatorial Counting

Kirchhoff introduced the theorem while studying electrical networks: currents entering a junction must balance currents leaving it. That local conservation law is encoded by the graph Laplacian. The surprise is that the same matrix also knows how many global, cycle-free backbones connect every vertex.

What Exactly Is Being Counted?

For an undirected graph $G=(V,E)$, a spanning tree is a subset of edges that:

Deleting any edge from a spanning tree disconnects it; adding any unused edge creates exactly one cycle. The count of spanning trees is denoted $\tau(G)$.

Build the Laplacian from Local Information

For a simple undirected graph, let $A$ be the adjacency matrix and $D$ the diagonal degree matrix. The Laplacian is:

Every row sums to zero: degree on the diagonal is canceled by one $-1$ for each neighbor. Consequently $L\mathbf{1}=0$, so $L$ is singular and $\det(L)=0$. The zero determinant is not a failure—it reflects the fact that absolute electrical potential can be shifted by a constant without changing any voltage difference.

Kirchhoff’s Matrix–Tree Theorem

Choose any vertex $r$ and delete row $r$ and column $r$ from $L$. Call the resulting $(n-1)\times(n-1)$ principal minor $L^{(r)}$. Then:

The answer does not depend on which vertex is deleted. If $G$ is disconnected, every such determinant is zero; if $G$ is connected, each is the same positive integer.

flowchart TD
    G[Graph edges] --> L[Build Laplacian L = D − A]
    L --> S[Delete one matching row and column]
    S --> D[Compute the cofactor determinant]
    D --> T[Result is the spanning-tree count]

Worked Example: A Square with One Diagonal

Use the graph from the first figure, with edges $\{12,23,34,41,13\}$. Its vertex degrees are $(3,2,3,2)$, so:

Delete row $4$ and column $4$. The cofactor is:

Expanding the determinant gives $15-4-3=8$. The theorem has counted all eight backbones without listing any of them.

Why a Determinant Counts Trees

The cleanest proof intuition uses an oriented incidence matrix. Give every undirected edge an arbitrary direction and create a matrix $B$ with one column per edge: the column has $+1$ at one endpoint, $-1$ at the other, and zero elsewhere. The chosen orientations are only bookkeeping.

Delete the row of a reference vertex $r$ from $B$ to obtain $B_r$. Then $L^{(r)}=B_rB_r^\mathsf{T}$. Cauchy–Binet expands the determinant as a sum over every subset $S$ of exactly $n-1$ edge columns:

The determinant is therefore a filter: it examines every $(n-1)$-edge subset algebraically, gives one vote to each spanning tree, and zero to everything else. Squaring removes the arbitrary incidence orientation signs.

Weighted, Parallel, and Directed Variants

The determinant framework adapts naturally, but the meaning of each entry must match the graph model.

Self-loops never belong to a spanning tree. The safest implementation simply ignores them while building the Laplacian. For directed graphs, always state the adjacency orientation and degree convention; transposing a definition swaps which arborescence orientation is counted.

Implementation with Exact Arithmetic

For integer or integer-weighted graphs, the answer is an integer and may be enormous. Fraction-free Bareiss elimination keeps every intermediate value integral and avoids the rounding risk of a floating-point determinant.

def bareiss(matrix):
    n = len(matrix)
    if n == 0:
        return 1
    a = [row[:] for row in matrix]
    previous = 1
    sign = 1

    for k in range(n - 1):
        if a[k][k] == 0:
            pivot_row = next((r for r in range(k + 1, n)
                              if a[r][k] != 0), None)
            if pivot_row is None:
                return 0
            a[k], a[pivot_row] = a[pivot_row], a[k]
            sign = -sign

        pivot = a[k][k]
        for i in range(k + 1, n):
            for j in range(k + 1, n):
                a[i][j] = (a[i][j] * pivot
                           - a[i][k] * a[k][j]) // previous
            a[i][k] = 0
        previous = pivot
    return sign * a[-1][-1]

def spanning_tree_count(n, edges):
    if n == 0:
        return 0
    laplacian = [[0] * n for _ in range(n)]
    for u, v, weight in edges:
        if u == v:
            continue
        laplacian[u][u] += weight
        laplacian[v][v] += weight
        laplacian[u][v] -= weight
        laplacian[v][u] -= weight
    minor = [row[:-1] for row in laplacian[:-1]]
    return bareiss(minor)

edges = [(0,1,1), (1,2,1), (2,3,1), (3,0,1), (0,2,1)]
print(spanning_tree_count(4, edges))  # 8

#include <boost/multiprecision/cpp_int.hpp>
#include <utility>
#include <vector>
using boost::multiprecision::cpp_int;
using Matrix = std::vector<std::vector<cpp_int>>;

cpp_int bareiss(Matrix a) {
    int n = static_cast<int>(a.size());
    if (n == 0) return 1;
    cpp_int previous = 1, sign = 1;

    for (int k = 0; k + 1 < n; ++k) {
        int row = k;
        while (row < n && a[row][k] == 0) ++row;
        if (row == n) return 0;
        if (row != k) {
            std::swap(a[row], a[k]);
            sign = -sign;
        }
        cpp_int pivot = a[k][k];
        for (int i = k + 1; i < n; ++i) {
            for (int j = k + 1; j < n; ++j)
                a[i][j] = (a[i][j] * pivot
                         - a[i][k] * a[k][j]) / previous;
            a[i][k] = 0;
        }
        previous = pivot;
    }
    return sign * a[n - 1][n - 1];
}

import java.math.BigInteger;

public class MatrixTree {
static BigInteger bareiss(BigInteger[][] input) {
    int n = input.length;
    if (n == 0) return BigInteger.ONE;
    BigInteger[][] a = new BigInteger[n][];
    for (int i = 0; i < n; i++) a[i] = input[i].clone();
    BigInteger previous = BigInteger.ONE;
    int sign = 1;

    for (int k = 0; k + 1 < n; k++) {
        int row = k;
        while (row < n && a[row][k].signum() == 0) row++;
        if (row == n) return BigInteger.ZERO;
        if (row != k) {
            BigInteger[] temp = a[row]; a[row] = a[k]; a[k] = temp;
            sign = -sign;
        }
        BigInteger pivot = a[k][k];
        for (int i = k + 1; i < n; i++) {
            for (int j = k + 1; j < n; j++) {
                a[i][j] = a[i][j].multiply(pivot)
                    .subtract(a[i][k].multiply(a[k][j]))
                    .divide(previous);
            }
            a[i][k] = BigInteger.ZERO;
        }
        previous = pivot;
    }
    BigInteger result = a[n - 1][n - 1];
    return sign > 0 ? result : result.negate();
}
}

Why Count Spanning Trees?

Laplacian cofactors also appear in network synchronization, determinant-based probabilistic models, and analyses of graph sparsification. The theorem is valuable because it turns an exponentially large family of trees into one polynomial-size determinant.

Pitfalls That Produce the Wrong Count

Complexity, Scale, and Algorithm Choice

Building a dense Laplacian costs $O(n^2+m)$ storage work, while dense determinant elimination uses $O(n^3)$ arithmetic operations and $O(n^2)$ memory. Exact integers can grow to many bits, so bit complexity may dominate even when the operation count looks modest.