Matrix Tree Theorem

Purpose: Count spanning trees of a graph as a determinant. This is the general statement; Kirchhoff’s theorem is the classical undirected case.

Undirected version

Build the Laplacian $L=D-A$, where $D$ is the diagonal degree matrix and $A$ the adjacency matrix. Then:

$\#\{\text{spanning trees}\}=\det \left(L_{\hat{i}\hat{i}}\right)$

for any $i$, where $L_{\hat{i}\hat{i}}$ deletes row $i$ and column $i$. All such cofactors are equal.

Weighted version. Set $A_{uv}={\sum }_{e=(u,v)}{w}_e$ and $D_{uu}={\sum }_v{A}_{uv}$. The same cofactor now computes
${\sum }_{T\text{ spanning tree}}{\prod }_{e\in T}{w}_e,$
which counts trees when all $w_e=1$, and is the tool for “sum over spanning trees” problems.

Directed version (Tutte)

For counting arborescences rooted at $r$ (every vertex reaches $r$, or $r$ reaches every vertex, depending on orientation):

• in-trees (all edges point toward $r$): use $L^{out}=D^{out}-A$ and delete row/column $r$;
• out-trees (all edges point away from $r$): use $L^{in}=D^{in}-A$ and delete row/column $r$.

$\#\{\text{arborescences rooted at }r\}=\det \left(L_{\hat{r}\hat{r}}\right).$

Unlike the undirected case, the cofactor depends on $r$ — different roots give different counts.

Code

// count spanning trees mod p (p prime), n <= ~300
long long countSpanningTrees(int n, vector<vector<long long>> L, long long MOD) {
    // delete last row and column
    int m = n - 1;
    long long det = 1;
    for (int i = 0; i < m; i++) {
        int piv = -1;
        for (int r = i; r < m; r++) if (L[r][i] % MOD) { piv = r; break; }
        if (piv < 0) return 0;
        if (piv != i) { swap(L[piv], L[i]); det = MOD - det; }
        det = det * L[i][i] % MOD;
        long long inv = powmod(L[i][i], MOD - 2, MOD);
        for (int c = i; c < m; c++) L[i][c] = L[i][c] * inv % MOD;
        for (int r = i + 1; r < m; r++) {
            long long f = L[r][i];
            if (!f) continue;
            for (int c = i; c < m; c++)
                L[r][c] = (L[r][c] - f * L[i][c]) % MOD;
        }
    }
    return (det % MOD + MOD) % MOD;
}

Build $L$ with L[u][u]++, L[v][v]++, L[u][v]--, L[v][u]-- for each undirected edge (all taken mod MOD, so use (x % MOD + MOD) % MOD).

Complexity

• $O(n^3)$ Gaussian elimination
• Over a prime field, use modular inverses; over the integers, use the Bareiss algorithm to keep entries bounded

Consequences

• Cayley’s formula. For $K_n$, the Laplacian is $nI-J$; a cofactor gives $n^{n-2}$ labelled trees on $n$ vertices — the shortest known proof.
• Complete bipartite graph. $K_{m,n}$ has $m^{n-1}{n}^{m-1}$ spanning trees.
• Number of Eulerian circuits — the BEST theorem combines the arborescence count with $\prod ({\mathrm{deg}}^{out}(v)-1)!$.
• Effective resistance. $R_{uv}=\frac{\det (L\text{ with }u,v\text{ deleted})}{\det (L\text{ with one deleted})}$, connecting spanning trees to electrical networks.

Variants / Use Cases

• Kirchhoff’s Theorem — the undirected statement in detail
• Prüfer codes — a bijective proof of Cayley’s formula, and the way to sample random labelled trees
• Chu-Liu/Edmonds — finds the minimum arborescence rather than counting them
• Random spanning tree sampling — Wilson’s algorithm (loop-erased random walk) samples uniformly without any determinant
• Counting problems mod a prime — the standard contest framing, since the true count is astronomically large