The Matrix--Tree Theorem Uses a Laplacian Cofactor

Any principal cofactor of the graph Laplacian counts spanning trees. Keeping the exact identity in view prevents the geometric or probabilistic intuition from drifting.

The data

Graph invariants often satisfy deletion--contraction recurrences. The chromatic polynomial $P_G(q)$ and Tutte polynomial $T_G(x,y)$ package many counts into algebraic form.

$$ L=D-A $$

There are two layers here: the object $\mathsf D$ and the law $\mathsf C$. Writing them separately makes the direction of $\Longrightarrow$ visible and keeps an accidental converse from slipping in.

$$ \tau(G)=\det L^{(i)} $$

Derivation

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ G=K_3:\qquad L=\begin{pmatrix}2&-1&-1\\-1&2&-1\\-1&-1&2\end{pmatrix},\qquad\det\begin{pmatrix}2&-1\\-1&2\end{pmatrix}=3 $$

Invariant content

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad L=D-A,\\[5pt] \mathsf{C}\;&:\quad \tau(G)=\det L^{(i)}. \end{aligned} $$

Scope

Deletion--contraction must distinguish loops and bridges. Applying the generic edge recurrence to either special case changes the invariant incorrectly.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \tau(G)=\det L^{(i)} \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Sat 22 November 2014. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.

The Matrix--Tree Theorem Uses a Laplacian Cofactor by Vicfred

The data

Derivation

Invariant content

Scope