CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The matrix-tree theorem becomes an eigenvalue product formula

Statement

Let $G$ be a finite simple graph on $n \geq 2$ vertices, and let

$0 = μ_{1} \leq μ_{2} \leq \dots \leq μ_{n}$

be the eigenvalues of its Laplacian matrix. Then

$τ (G) = \frac{1}{n} \prod_{j = 2}^{n} μ_{j} .$

If $G$ is $d$ -regular with adjacency eigenvalues $d = λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$ , then

$τ (G) = \frac{1}{n} \prod_{j = 2}^{n} (d - λ_{j}) .$

Facts & Assumptions

Given: A finite simple graph $G$ on $n \geq 2$ vertices with Laplacian $L$ and spanning-tree count $τ (G)$ .

[L1]

Every principal cofactor of $L$ equals $τ (G)$ (Kirchhoff's matrix-tree theorem).

[L2]

The determinant of a square matrix is the product of its eigenvalues, counted with multiplicity (If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $\det (T) = \prod_{i < n} λ_{i}$ : determinant is the product of the eigenvalues counted with algebraic multiplicity).

[L3]

If $p$ is a polynomial and $λ$ is an eigenvalue of $A$ , then $p (λ)$ is an eigenvalue of $p (A)$ with the same eigenvectors (If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $χ_{p (T)} (y) = \prod_{i < n} (y - p (λ_{i}))$ for every $p \in F [x]$ : the eigenvalues of $p (T)$ are $p (λ_{i})$ , counted with algebraic multiplicity).

[F1]

The adjacency spectrum records the eigenvalues of the adjacency matrix (Adjacency spectrum, spectral radius, and cospectral graphs).

Proof

technique · direct

1.1L1L2algebra

Expanding the characteristic polynomial $\det (t I - L)$ at $t = 0$ shows that the coefficient of $t$ is $(- 1)^{n - 1} \sum_{i = 1}^{n} \det L^{(i)}$ . By [L1], this is $(- 1)^{n - 1} n τ (G)$ . On the other hand, [L2] gives $\det (t I - L) = \prod_{j = 1}^{n} (t - μ_{j}) = t \prod_{j = 2}^{n} (t - μ_{j})$ , so the same coefficient of $t$ is $(- 1)^{n - 1} \prod_{j = 2}^{n} μ_{j}$ . Therefore $n τ (G) = \prod_{j = 2}^{n} μ_{j}$ .

2.1step 1.1L3F1

If $G$ is $d$ -regular, then $L = d I - A$ . Applying [L3] to the polynomial $p (x) = d - x$ shows that the Laplacian eigenvalues are $d - λ_{1}, \dots, d - λ_{n}$ . Since $λ_{1} = d$ , the zero Laplacian eigenvalue is $d - λ_{1}$ , and substituting the others into step 1.1 gives $τ (G) = \frac{1}{n} \prod_{j = 2}^{n} (d - λ_{j})$ .

3.1step 1.1step 2.1∎

Steps 1.1 and 2.1 are exactly the two displayed formulas.

Depends on

Used by

Cayley's formula follows again from the matrix-tree theorem Corollary
Kirchhoff's formula gives τ(K₄)=16 Example

Dependency tree · two levels

27 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Richard P. Stanley, MIT 18.314 handout, Corollary 1.10 (standard reference, not scraped)