The Matrix-Tree Theorem

Counting spanning trees by taking a determinant. Build the Laplacian L of a multidigraph — out-degrees down the diagonal, minus the number of arcs elsewhere — delete the row and column of a chosen vertex r, and the determinant of what is left is the number of spanning arborescences rooted to r:

(# of spanning arborescences of D rooted to r) = det(L∼r,∼r)

The full Laplacian is useless for this, and grinberg-graph-theory says why before stating the theorem: its determinant is always 0, because its rows sum to zero. When a matrix has determinant 0, its largest nonzero minors are "the closest the matrix has" to a nonzero determinant, and here they turn out to count something.

Why it matters in this corpus

This is where linear-algebra stops being a prerequisite and starts doing the work. The whole of graph-theory as Grinberg teaches it needs one non-graph tool — determinants — and Chapter 5 spends 65 pages cashing it in. Nothing else in his book asks for machinery from another subject.

The pattern is one this spoke has recorded once already, in markov-chain: a finite combinatorial object is identified with a matrix, and then matrix facts become facts about the object. Two subjects, same move.

Cayley's formula, and who actually proved it

The first application is the number of labelled trees on n vertices:

(# of spanning trees of Kₙ) = n^(n−2)

Grinberg gets it by evaluating one determinant, and then adds a note the corpus should keep: the result is "widely known as Cayley's formula, despite its earlier discovery by Borchardt in 1860," whose proof is close to the one given. He also points at four other routes to the same formula — two combinatorial proofs in Galvin, Joyal's, three in Stanley, four more in Aigner and Ziegler — which is the clearest illustration in this spoke of a fact with many independent proofs, none of them canonical.

The BEST theorem

The directed cousin, and the reason arborescences get so much room. For a balanced multidigraph, the number of Eulerian circuits ending with a fixed arc a is

ε(D, a) = τ(D, r) · ∏ (deg⁻ u − 1)!

where τ is the number of spanning arborescences rooted from r, the target of a. Grinberg introduces it with "we now come to something much more surprising," and it is: Eulerian circuits are a walk question, arborescences are a subgraph question, and there is no reason from the definitions that one should count the other.

Chaining BEST with the Matrix-Tree Theorem turns a counting problem about walks into a determinant. The worked payoff is de Bruijn sequences — cyclic strings containing every length-n word over an alphabet exactly once — whose existence and count both fall out this way. That is the one place in the book where the algebraic machinery produces an object a programmer might already have needed.

Variants held

• Undirected Matrix-Tree Theorem (§5.15) — the classical form, a special case of the directed one here rather than the starting point; its eigenvalue version counts spanning trees of Kₙ,ₘ and of the hypercube.
• Weighted Matrix-Tree Theorem (§5.19) — arcs carry weights, the determinant becomes a generating function, and specialising the weights counts trees by their degree sequence (a refined Cayley's formula).
• Laplacian nullspace (§5.18) — the left nullspace, and a harmonic-vector statement in the weighted case.

Connections

• grinberg-graph-theory — the source; §§5.9–5.19
• graph-theory — the subject
• linear-algebra — determinants, minors, eigenvalues
• markov-chain — the other finite-object-as-matrix page here