Counting Spanning Trees

A spanning tree of a graph is a way to keep every vertex connected using the fewest possible edges and no cycles. Think of a network of cities: a spanning tree is a minimal set of roads that still lets you drive between any two of them.

A single graph usually has many spanning trees. A humble 4×4 grid already has 100,352 of them; a complete graph on just 10 vertices has 100,000,000 (that's $10^{8}$). Listing them one by one quickly becomes hopeless — the count grows faster than any computer could ever enumerate.

So here is the puzzle: how many spanning trees does a graph have, without drawing a single one? It sounds like it should require enumeration. It doesn't. There is an exact, fast formula — and it comes from an unexpected place: a determinant.

Click pairs of dots to add or remove edges. With each change, the panel rebuilds the Laplacian matrix, deletes one row and column, and takes the determinant — and out pops the exact number of spanning trees. No enumeration anywhere.

<p class="hint">{{hint}}</p>
<div class="stage">
  <svg id="graph" viewBox="0 0 280 220" aria-label="{{graph_aria}}"></svg>
  <div class="panel">
    <div class="count">{{spanning_trees_label}} <span id="count">0</span></div>
    <div class="sub">{{sub_label}}</div>
    <div id="matrix" class="matrix"></div>
  </div>
</div>
<div class="btns">
  <button id="cycle" type="button">{{btn_cycle}}</button>
  <button id="complete" type="button">{{btn_complete}}</button>
  <button id="clear" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.stage { display: flex; gap: 1rem; flex-wrap: wrap; align-items: flex-start; }
#graph { width: 280px; height: 220px; background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px; touch-action: manipulation; }
.node { fill: #1d3557; cursor: pointer; transition: fill .12s, r .12s; }
.node:hover { fill: #2a4d7a; }
.node.sel { fill: #e63946; }
.nlabel { fill: #fff; font: 700 12px ui-monospace, monospace; pointer-events: none; text-anchor: middle; dominant-baseline: central; }
.edge { stroke: #1d3557; stroke-width: 2.4; cursor: pointer; }
.panel { flex: 1; min-width: 200px; }
.count { font-size: 1.15rem; font-weight: 700; color: #0a7d33; }
.sub { font-size: .8rem; color: #667; margin: .1rem 0 .6rem; }
.matrix { font: 600 13px ui-monospace, monospace; color: #1d3557; white-space: pre; background: #eef3f7; border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .6rem; overflow-x: auto; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .8rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice how the count can leap from a handful to thousands with one extra edge, yet the determinant is computed in the blink of an eye. This is Kirchhoff's Matrix-Tree theorem at work: a hard-looking counting problem solved by one clean piece of linear algebra. Compare this to problems like P vs NP, where counting really does seem to be intractable.

Most counting questions in graph theory are brutally hard. Counting the number of perfect matchings, or the number of Hamiltonian cycles, is #P-hard — believed to be far beyond polynomial time. Counting spanning trees feels like it should join that club. It doesn't.

• The status: solved, and efficiently. In 1847, the physicist Gustav Kirchhoff — yes, the circuits one — proved the Matrix-Tree theorem while studying electrical networks.
• The recipe. Build the Laplacian matrix L = D − A, where D lists each vertex's degree on the diagonal and A is the adjacency matrix. Delete any one row and the matching column. The determinant of what remains is exactly the number of spanning trees.
• Why it's fast. A determinant of an n×n matrix is computable in about $n^{3}$ steps by Gaussian elimination. So counting spanning trees is polynomial time — even when the count itself is astronomically large.
• A famous special case. For the complete graph on n vertices the theorem collapses to Cayley's formula: exactly $n^{n-2}$ spanning trees.

That is the surprise: a counting problem that looks exponential is secretly linear algebra. It sits firmly in P, a rare and beautiful exception among the #P-hard counting problems that surround it.

The Matrix-Tree theorem is not a curiosity — the Laplacian determinant turns up across science and engineering:

• Network reliability: the number (and weighting) of spanning trees measures how robustly a network stays connected as links fail.
• Electrical circuits: Kirchhoff discovered it analyzing resistor networks; effective resistance between two nodes is a ratio of such determinants.
• Statistical physics: counting spanning trees connects to partition functions and models on lattices.
• Randomized algorithms: the same Laplacian machinery lets you sample a spanning tree uniformly at random — the engine behind maze generation and Markov-chain methods.

Understanding spanning trees is also the gateway to their optimization cousin, the minimum spanning tree, where instead of counting you hunt for the cheapest tree of all.

Counting spanning trees should be hopeless — the trees outnumber the atoms in your hardware long before the graph gets large. Yet Kirchhoff's Matrix-Tree theorem counts every one of them with a single determinant, in polynomial time, without ever drawing a tree.

It is a quiet lesson about computation: hardness is not always intrinsic. Sometimes a problem only looks exponential until you find the right structure — here, the Laplacian — that dissolves it. Most counting problems, like those lurking near P vs NP, never get this lucky. Spanning trees did.