xv. Matrix-Tree Theorem

The number of spanning trees is a determinant. For an undirected multigraph with Laplacian $L=D-A$ ($A_{uv}$ = number of $u$–$v$ edges, loops ignored), every cofactor $\det L_{\hat{i}\hat{i}}$ (delete row and column $i$) equals the number of spanning trees. With edge weights in $A$ it is ${\sum }_T{\prod }_{e\in T}{w}_e$. For directed graphs (Tutte), arborescences into root $r$ are counted by deleting row/column $r$ of $D_{\text{out}}-A$, and arborescences out of $r$ by $D_{\text{in}}-A$. Determinants are in Determinants.

ll detMod(vector<vector<ll>> a, ll p) {                     // O(n^3), p prime, entries in [0, p)
    int n = sz(a); ll det = 1;
    for (int c = 0; c < n; c++) {
        int piv = -1; for (int r = c; r < n; r++) if (a[r][c]) { piv = r; break; }
        if (piv < 0) return 0;
        if (piv != c) swap(a[piv], a[c]), det = (p - det) % p;
        det = det * a[c][c] % p;
        ll inv = 1; for (ll b = a[c][c], e = p - 2; e; e >>= 1, b = b * b % p) if (e & 1) inv = inv * b % p;
        for (int r = c + 1; r < n; r++) if (a[r][c]) {
            ll f = a[r][c] * inv % p;
            for (int k = c; k < n; k++) a[r][k] = (a[r][k] - f * a[c][k] % p + p) % p;
        }
    }
    return det;
}
ll countSpanningTrees(int n, const vector<array<ll, 3>>& E, ll p) {   // {u, v, weight}; undirected
    if (n == 1) return 1;
    vector<vector<ll>> L(n, vector<ll>(n));
    auto add = [&](int i, int j, ll x) { L[i][j] = ((L[i][j] + x) % p + p) % p; };
    for (auto [u, v, w] : E) if (u != v) add(u, u, w), add(v, v, w), add(u, v, -w), add(v, u, -w);
    vector<vector<ll>> M(n - 1, vector<ll>(n - 1));
    for (int i = 1; i < n; i++) for (int j = 1; j < n; j++) M[i - 1][j - 1] = L[i][j];
    return detMod(M, p);
}
ll countArborescences(int n, int r, const vector<array<ll, 3>>& E, ll p, bool outTree) {   // directed u -> v
    vector<vector<ll>> L(n, vector<ll>(n));
    for (auto [u, v, w] : E) if (u != v) {
        int d = outTree ? v : u;                             // out-trees: in-degree on the diagonal
        L[d][d] = (L[d][d] + w) % p; L[u][v] = ((L[u][v] - w) % p + p) % p;
    }
    vector<vector<ll>> M; for (int i = 0; i < n; i++) if (i != r) { M.push_back({}); for (int j = 0; j < n; j++) if (j != r) M.back().push_back(L[i][j]); }
    return n == 1 ? 1 : detMod(M, p);
}

Over the integers (exact, no modulus) use fraction-free Bareiss elimination; the count can be huge, so contest problems ask modulo a prime.

Proof: Cauchy–Binet

Orient each edge arbitrarily and let $B$ be the $n\times m$ incidence matrix ($+1$ at the head, $-1$ at the tail, weighted version: scale column $e$ by $\sqrt{w_e}$). Then $L=B{B}^T$ and deleting row $i$ of $B$ gives $B^{\prime }$ with $L_{\hat{i}\hat{i}}=B^{\prime }{B}^{\prime T}$. Cauchy–Binet: $\det (B^{\prime }{B}^{\prime T})={\sum }_S\det (B_S^{\prime }{)}^2$ over $(n-1)$-subsets $S$ of edges. If $S$ contains a cycle, the columns of the cycle (signed around it) sum to zero, so $\det B_S^{\prime }=0$. If $S$ is a spanning tree, some vertex $\ne i$ is a leaf of $S$; its row has a single $\pm 1$, and expanding along it reduces to the tree with that leaf removed, so by induction $\det B_S^{\prime }=\pm 1$ (weighted: $\pm \prod \sqrt{w_e}$). Hence the cofactor is ${\sum }_T{\prod }_{e\in T}{w}_e$. If $S$ has $n-1$ edges and no cycle it is a spanning tree, so these are all cases.
Directed: for in-trees into $r$, write $L=D_{\text{out}}-A$ and expand the reduced determinant by choosing one out-edge per non-root vertex (each row is “out-degree minus out-neighbours”); choices containing a cycle cancel in pairs by a sign-reversing involution on the cycles, leaving exactly the choices that form an in-tree, each with sign $+1$. Out-trees are the transpose.

Consequences

Graph	Spanning trees
$K_n$	$n^{n-2}$ (Cayley)
$K_{m,n}$	$m^{n-1}{n}^{m-1}$
cycle $C_n$	$n$
wheel $W_n$ ($n$ rim vertices)	$L_{2n}-2$ (Lucas numbers)
hypercube $Q_d$	$2^{2^d-d-1}{\prod }_{k=1}^d{k}^{\left(\genfrac{}{}{0ex}{}{d}{k}\right)}$
$K_n$ with a forest $F$ of $k$ trees of sizes $s_i$ forced in	$n^{k-2}\prod s_i$

• Count MSTs: process weight classes in increasing order; for class $w$, contract all lighter edges (DSU), and in each connected component of the class’s edges on the contracted vertices count spanning trees; multiply over all classes and components.
• Sum over spanning trees of the total edge weight: $\frac{d}{dx}\det (L_{\hat{i}\hat{i}}(1+xw)){|}_{x=0}=\tau \cdot \mathrm{tr}(L_0^{-1}{L}_w)$ where $L_0$ is the unweighted reduced Laplacian ($\tau =\det L_0\ne 0$) and $L_w$ the reduced Laplacian with weights $w$; equivalently compute the determinant over ${\mathbb{F}}_p[x]/(x^2)$.
• Probability that edge $e$ is in a uniform random spanning tree = $w_e\cdot R_{\text{eff}}(e)$ (effective resistance), and $\tau (G-e)=\tau (G)(1-w_e{R}_e)$. Effective resistance itself is also a determinant ratio: $R_{uv}=\det (L\text{ with both }u,v\text{ deleted})/\det (L_{\hat{i}\hat{i}})$ for any single-deleted cofactor.
• Eulerian circuits (BEST theorem): $\text{ec}(G)=t_w(G){\prod }_v({\mathrm{deg}}^{+}(v)-1)!$ for a connected Eulerian digraph, where $t_w$ is the number of arborescences into any fixed vertex $w$ (Euler Tours).
• Random spanning trees: Wilson’s algorithm (loop-erased random walks) samples uniformly without determinants; Aldous–Broder (first-entrance edges of a random walk) too.

Proof: Cayley and the MST count

Cayley: the reduced Laplacian of $K_n$ is $nI-J$ of size $n-1$ ($J$ all ones), with eigenvalues $n$ (multiplicity $n-2$) and $n-(n-1)=1$, so $\det =n^{n-2}$. Counting MSTs: Kruskal’s runs on all tie-breaking orders produce exactly the MSTs; before class $w$ the DSU components are fixed, and within the class any spanning forest of the class edges over the contracted components can be chosen independently per component of that multigraph. So the number of MSTs is the product over classes and components of the number of spanning trees of the contracted multigraph, each given by the matrix-tree theorem.