Total Number of Spanning Trees (Kirchhoff)

Total Number of Spanning Trees asks: given an undirected graph, how many different spanning trees does it have? A brute-force enumeration explodes, but a 19th-century result — Kirchhoff's matrix-tree theorem — turns the whole thing into a single determinant.

The slow way first

The naive idea: enumerate every subset of n − 1 edges, and for each one check whether it forms a spanning tree (connected, acyclic, touches all vertices). With m edges that is C(m, n−1) subsets — exponential. Even a modest graph with 20 edges and 10 vertices has millions of subsets to test. We need a closed form.

The question to ask: is there a single algebraic quantity that already encodes the count? There is — the determinant of a matrix built straight from the graph.

The idea: Kirchhoff's matrix-tree theorem

Build the Laplacian matrix L = D − A, where D is the diagonal matrix of vertex degrees and A is the adjacency matrix. Then delete any one row and its matching column, and take the determinant of what remains. That determinant is the number of spanning trees — no enumeration required.

It does not matter which row and column you delete — every choice gives the same determinant. That is the surprising part of the theorem.

Walk through it

Step through the animation. First the degrees go on the diagonal, then each edge places a −1 off-diagonal — notice every row sums to zero, the hallmark of a Laplacian. We delete row 0 and column 0, leaving a 3×3 cofactor over vertices 1, 2, 3. Its determinant comes out to 8, so the graph has 8 spanning trees.

Pseudocode

build degree array deg and adjacency matrix A from the edges
build L (n x n): L[i][i] = deg[i]; L[i][j] = -A[i][j] for i != j
M = L with row 0 and column 0 removed       # any single index works
return determinant(M)                        # = number of spanning trees

The Python solution

def count_spanning_trees(n, edges):
    deg = [0] * n
    A = [[0] * n for _ in range(n)]
    for u, v in edges:
        A[u][v] = A[v][u] = 1
        deg[u] += 1
        deg[v] += 1
    L = [[0] * n for _ in range(n)]
    for i in range(n):
        L[i][i] = deg[i]
    for i in range(n):
        for j in range(n):
            if i != j:
                L[i][j] = -A[i][j]
    # delete row 0 and column 0
    M = [row[1:] for row in L[1:]]
    # number of spanning trees = det of the cofactor
    return round(determinant(M))

• deg and A are filled in one pass over the edge list; each undirected edge bumps two degrees and two adjacency cells.
• L[i][i] = deg[i] places the degrees on the diagonal — this is the matrix D.
• The double loop subtracts A, putting −1 wherever an edge exists. After this, every row of L sums to zero.
• M = [row[1:] for row in L[1:]] deletes row 0 and column 0 — the cofactor step.
• The determinant of M is the answer; round cleans up floating-point error from the determinant routine.

Complexity

We trade O(n²) space (the matrix) for a polynomial running time: the cost is dominated by the O(n³) determinant via Gaussian elimination, regardless of how many spanning trees exist.

When this pattern shows up

Practice