Introduction

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 10810^{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.

Build a Graph

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">Click two dots to add or remove an edge. The panel rebuilds the
<b>Laplacian</b>, deletes one row &amp; column, and takes the <b>determinant</b> —
that single number is the exact count of spanning trees. No enumeration.</p>
<div class="stage">
  <svg id="graph" viewBox="0 0 280 220" aria-label="graph"></svg>
  <div class="panel">
    <div class="count">Spanning trees: <span id="count">0</span></div>
    <div class="sub">det of the reduced Laplacian</div>
    <div id="matrix" class="matrix"></div>
  </div>
</div>
<div class="btns">
  <button id="cycle" type="button">Make a 5-cycle</button>
  <button id="complete" type="button">Make K5 (complete)</button>
  <button id="clear" type="button" class="ghost">Clear edges</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; }

// Kirchhoff's Matrix-Tree theorem. Build the Laplacian L = D - A of an
// undirected graph, delete any one row and the matching column, and the
// DETERMINANT of the remaining (n-1)x(n-1) matrix is EXACTLY the number of
// spanning trees. No enumeration — just one determinant (computable in ~n^3).
const N = 5;
// pentagon layout of the 5 nodes
const POS = [];
for (let i = 0; i < N; i++) {
  const a = -Math.PI / 2 + i * 2 * Math.PI / N;
  POS.push([140 + 88 * Math.cos(a), 110 + 80 * Math.sin(a)]);
}
const edges = new Set();          // "i,j" with i<j
const ekey = (a, b) => a < b ? a + ',' + b : b + ',' + a;
let sel = -1;

function toggleEdge(a, b) {
  if (a === b) return;
  const k = ekey(a, b);
  edges.has(k) ? edges.delete(k) : edges.add(k);
}

// Determinant by fraction-free Gaussian elimination on integers (exact).
function det(M) {
  const n = M.length;
  if (n === 0) return 1;
  const A = M.map(r => r.slice());
  let sign = 1, prev = 1;
  for (let k = 0; k < n - 1; k++) {
    if (A[k][k] === 0) {
      let sw = -1;
      for (let i = k + 1; i < n; i++) if (A[i][k] !== 0) { sw = i; break; }
      if (sw === -1) return 0;
      [A[k], A[sw]] = [A[sw], A[k]]; sign = -sign;
    }
    for (let i = k + 1; i < n; i++)
      for (let j = k + 1; j < n; j++)
        A[i][j] = (A[i][j] * A[k][k] - A[i][k] * A[k][j]) / prev;
    prev = A[k][k];
  }
  return sign * A[n - 1][n - 1];
}

function laplacian() {
  const L = Array.from({ length: N }, () => Array(N).fill(0));
  for (const k of edges) {
    const [i, j] = k.split(',').map(Number);
    L[i][i]++; L[j][j]++; L[i][j]--; L[j][i]--;
  }
  return L;
}

function countTrees() {
  const L = laplacian();
  // delete row 0 and column 0
  const M = [];
  for (let i = 1; i < N; i++) M.push(L[i].slice(1));
  return { value: det(M), reduced: M };
}

function render() {
  const svg = document.getElementById('graph');
  svg.innerHTML = '';
  const NS = 'http://www.w3.org/2000/svg';
  for (const k of edges) {
    const [i, j] = k.split(',').map(Number);
    const ln = document.createElementNS(NS, 'line');
    ln.setAttribute('x1', POS[i][0]); ln.setAttribute('y1', POS[i][1]);
    ln.setAttribute('x2', POS[j][0]); ln.setAttribute('y2', POS[j][1]);
    ln.setAttribute('class', 'edge');
    ln.addEventListener('click', () => { toggleEdge(i, j); render(); });
    svg.appendChild(ln);
  }
  for (let i = 0; i < N; i++) {
    const c = document.createElementNS(NS, 'circle');
    c.setAttribute('cx', POS[i][0]); c.setAttribute('cy', POS[i][1]);
    c.setAttribute('r', 14);
    c.setAttribute('class', 'node' + (sel === i ? ' sel' : ''));
    c.addEventListener('click', () => {
      if (sel === -1) sel = i;
      else { toggleEdge(sel, i); sel = -1; }
      render();
    });
    svg.appendChild(c);
    const t = document.createElementNS(NS, 'text');
    t.setAttribute('x', POS[i][0]); t.setAttribute('y', POS[i][1]);
    t.setAttribute('class', 'nlabel'); t.textContent = i;
    svg.appendChild(t);
  }
  const { value, reduced } = countTrees();
  document.getElementById('count').textContent = value;
  document.getElementById('matrix').textContent =
    reduced.map(row => row.map(x => String(x).padStart(3)).join(' ')).join('\n')
    || '(empty)';
}

document.getElementById('cycle').addEventListener('click', () => {
  edges.clear(); sel = -1;
  for (let i = 0; i < N; i++) toggleEdge(i, (i + 1) % N);
  render();
});
document.getElementById('complete').addEventListener('click', () => {
  edges.clear(); sel = -1;
  for (let i = 0; i < N; i++) for (let j = i + 1; j < N; j++) edges.add(ekey(i, j));
  render();
});
document.getElementById('clear').addEventListener('click', () => {
  edges.clear(); sel = -1; render();
});

// start with a 5-cycle (exactly 5 spanning trees: drop any one of 5 edges)
for (let i = 0; i < N; i++) toggleEdge(i, (i + 1) % N);
render();
Result
Console

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.

The Real Complexity

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 n3n^{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 nn−2n^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/spanning-tree-counting/Content licensed under CC BY-NC 4.0.