Cayley's Formula and Matrix-Tree Theorem

We prove this by exhibiting an explicit bijection (the Prüfer correspondence) between the set $\mathcal{T}_n$ of labeled trees on $[n]$ and the set $\mathcal{S}_n = [n]^{n-2}$ of sequences of length $n-2$ over the alphabet $[n]$. Since $|\mathcal{S}_n| = n^{n-2}$, a bijection immediately gives $|\mathcal{T}_n| = n^{n-2}$.

The encoding map $\varphi: \mathcal{T}_n \to \mathcal{S}_n$. Fix a tree $T$ on $[n]$. We build a sequence of length $n-2$ by the following algorithm. 1. Set $T_1 = T$. 2. For $k = 1, 2, \dots, n-2$: let $\ell_k$ be the leaf of $T_k$ (a vertex of degree $1$) with the smallest label, let $a_k$ be its unique neighbor in $T_k$, record $a_k$ as the $k$-th term of the sequence, and set $T_{k+1} = T_k - \ell_k$ (delete the leaf $\ell_k$ and its incident edge). 3. Stop after $n-2$ steps; at that point $T_{n-1}$ has exactly $2$ vertices and $1$ edge. Every tree on $m \ge 2$ vertices has at least one leaf (a standard fact: the sum of degrees is $2(m-1) < 2m$, so not all degrees can be $\ge 2$), so step 2 is always well defined for $k \le n - 2$, since $T_k$ has $n - k + 1 \ge 3$ vertices when $k \le n-2$. This defines $\varphi(T) = (a_1, \dots, a_{n-2}) \in [n]^{n-2}$.

Key invariant. During the process, vertex $i$ is deleted as a leaf at some step if and only if it is not one of the two vertices surviving to the end, and the number of times $i$ appears among $a_1,\dots,a_{n-2}$ equals $\deg_T(i) - 1$. This is because each time $i$ is not yet deleted and some other leaf attached to $i$ is removed, $i$'s remaining degree in the current subtree drops by exactly one, and $i$ itself is recorded once for every neighbor removed before $i$ is removed (or, if $i$ survives to the end, once for every neighbor removed while $i$ is present). Summing, $i$ is recorded exactly $\deg_T(i) - 1$ times if $i$ is not among the last two vertices, and exactly $\deg_T(i) - 1$ times as well if $i$ is among the last two survivors (one of its edges — the final one — is never "recorded" because the process halts before deleting a leaf from the final 2-vertex tree). In all cases:

(Since $\sum_i \deg_T(i) = 2(n-1)$, the right side sums to $2(n-1) - n = n - 2$, consistent with the sequence having length $n-2$.)

The decoding map $\psi: \mathcal{S}_n \to \mathcal{T}_n$. Given $(a_1,\dots,a_{n-2}) \in [n]^{n-2}$, define $d_i = 1 + \#\{k : a_k = i\}$ for each $i \in [n]$; note $\sum_i d_i = n - 2 + n = 2n-2 = 2(n-1)$ and each $d_i \ge 1$. Reconstruct a candidate tree edge-by-edge: 1. Let $L = \{i \in [n] : d_i = 1\}$ ("current leaf pool"), maintained as we go. 2. For $k = 1,\dots, n-2$: let $\ell_k$ be the smallest element of $L$. Add edge $\{\ell_k, a_k\}$. Remove $\ell_k$ from $L$. Decrease $d_{a_k}$ by $1$; if $d_{a_k}$ becomes $1$, insert $a_k$ into $L$. 3. After the loop, exactly two labels remain with $d$-value $1$ (this must be checked); join them by an edge. We must verify (a) at every step $L$ is nonempty so $\ell_k$ is well defined, and (b) the output is a tree, and (c) $\varphi(\psi(a_1,\dots,a_{n-2})) = (a_1,\dots,a_{n-2})$ and $\psi(\varphi(T)) = T$. Well-definedness of the loop. At the start, $\sum d_i = 2(n-1)$ over $n$ positive integers, so by an averaging/counting argument at least two indices have $d_i = 1$ whenever $n \ge 2$ remain active (this is checked inductively: initially true since not all $d_i \geq 2$ as that would force $\sum d_i \ge 2n > 2(n-1)$). Each step of the loop removes one element from $L$ (namely $\ell_k$) and decreases exactly one $d$-value by $1$, possibly adding one new element to $L$; a direct inductive check (same degree-sum argument on the shrinking active vertex set, which always has size $n-k+1 \ge 2$ and $d$-values summing to $2(n-k) - ...$ — more simply, one tracks that the invariant "sum of $d_i$ over currently active vertices $= 2\cdot(\text{number of active vertices}) - 2$" is preserved) guarantees $L$ is always nonempty until exactly $2$ vertices remain, both with $d = 1$. The output is a tree. The construction adds exactly $n - 2$ edges in the loop plus $1$ final edge, for $n - 1$ edges total on $n$ vertices. We show the resulting graph is connected and acyclic by strong induction on $n$: the base case $n=2$ is trivial (single edge). For the inductive step, note $\ell_1$ is a leaf attached only to $a_1$ in the final construction (no other edge in the process ever touches $\ell_1$, since it is deleted from the leaf pool immediately and never re-inserted, being removed once and for all), and the remaining process on $\{a_1,\dots,a_{n-2}\}$ restricted appropriately reconstructs a tree on $[n]\setminus\{\ell_1\}$ by the inductive hypothesis (relabeling is unnecessary since the algorithm's rule depends only on numerical comparison, and removing $\ell_1$ together with reducing $d_{a_1}$ by one is exactly the decoding process for the sequence $(a_2,\dots,a_{n-2})$ on vertex set $[n]\setminus \{\ell_1\}$). Attaching the leaf $\ell_1$ to this tree via edge $\{\ell_1, a_1\}$ yields a tree on $[n]$. Hence $\psi$ produces a tree. Mutual inverses. By construction, running $\varphi$ on the tree $\psi(a_1,\dots,a_{n-2})$ removes leaves in exactly the same order $\ell_1, \ell_2, \dots$ (both processes pick, at each stage, the smallest-labeled current leaf, and both maintain identical leaf pools by the identical recursive rule), and records exactly $a_1, \dots, a_{n-2}$ as neighbors. Hence $\varphi \circ \psi = \mathrm{id}$. Conversely, given a tree $T$, feeding $\varphi(T)$ back into $\psi$ replays the leaf-deletion process of $\varphi$ in reverse and reattaches each deleted leaf to its recorded neighbor in the same order, reconstructing exactly $T$, since the degree bookkeeping $(\ast)$ guarantees the $d_i$ values computed by $\psi$ from $\varphi(T)$ match the true degrees of $T$ exactly. So $\psi \circ \varphi = \mathrm{id}$. Therefore $\varphi$ is a bijection between $\mathcal{T}_n$ and $[n]^{n-2}$, and

The $i$-th entry of $L\mathbf{1}$ is $\sum_j L_{ij} = L_{ii} + \sum_{j \ne i} L_{ij} = \deg(i) + \sum_{j: ij \in E}(-1) = \deg(i) - \deg(i) = 0$. So $L\mathbf{1} = 0$, meaning $\mathbf{1}$ is a nonzero vector in the kernel of $L$, so $L$ is singular and $\det L = 0$. $\blacksquare$

We prove this using the Cauchy–Binet formula, and an orientation-based factorization of $L$. The technique is: factor $L^{(i)} = M M^T$ for a suitable incidence-type matrix $M$, then expand the determinant of $M M^T$ as a sum of squares of maximal-minor determinants of $M$, and identify each nonzero minor with exactly one spanning tree.

Step 1: Oriented incidence matrix. Fix an arbitrary orientation of each edge of $G$ (assign each edge a "head" and "tail" vertex; the choice will not affect the final count). Let $m = |E|$, and let $B$ be the $n \times m$ oriented incidence matrix: for edge $e = (u \to v)$ (tail $u$, head $v$), column $e$ of $B$ has $+1$ in row $v$, $-1$ in row $u$, and $0$ elsewhere. (Any convention for sign works as long as it is used consistently; we take head $=+1$.) Claim: $B B^T = L$. Indeed, the $(i,j)$ entry of $BB^T$ is $\sum_{e \in E} B_{ie} B_{je}$. For $i = j$: each edge incident to $i$ contributes $(\pm 1)^2 = 1$ to this sum (only edges touching $i$ have $B_{ie}\ne 0$), so the diagonal entry is $\deg(i)$. For $i \ne j$: a term $B_{ie}B_{je}$ is nonzero only if edge $e$ has both endpoints in $\{i,j\}$, i.e. $e = ij$; if $ij \in E$, exactly one of $i,j$ is the head and the other the tail, contributing $(+1)(-1) = -1$; if $ij \notin E$ the sum is $0$. Hence off-diagonal entries are $-1$ exactly when $ij \in E$ and $0$ otherwise. This matches $L$ exactly, proving the claim: $L = BB^T$.

Step 2: Reduce to a submatrix. Fix $i \in [n]$ and let $B^{(i)}$ be $B$ with row $i$ deleted (an $(n-1) \times m$ matrix). Deleting row $i$ and column $i$ from $L = BB^T$ corresponds exactly to deleting row $i$ from $B$ (on both factors), so

This holds because the $(j,k)$ entry ($j,k \ne i$) of $L^{(i)}$ is the same dot product of rows $j,k$ of $B$ as before, unaffected by whether row $i$ of $B$ is present or not, since we are only reading off rows $j,k$.

Step 3: Cauchy–Binet formula. For an $(n-1) \times m$ matrix $X$ with $m \ge n-1$, the Cauchy–Binet formula states

where the sum ranges over all $S \subseteq E$ with $|S| = n-1$, and $X_S$ denotes the $(n-1)\times(n-1)$ submatrix of $X$ using only the columns indexed by $S$. (This is a standard identity of multilinear algebra, provable by expanding both sides via the Leibniz determinant formula and matching terms through the Binet–Cauchy combinatorial identity for products of minors; we take it as a known prerequisite tool from linear algebra, analogous to but independent of the graph-theoretic content being proved here.) Applying this with $X = B^{(i)}$:

Step 4: Identify each term. We claim that for a subset $S \subseteq E$ with $|S| = n-1$:

Case A: $(V,S)$ is not a spanning tree. Since $|S| = n - 1$ and $(V,S)$ is not a spanning tree, $(V,S)$ must contain a cycle (a graph on $n$ vertices with $n-1$ edges is a spanning tree iff it is acyclic iff it is connected — these are standard equivalent characterizations from the theory of Spanning Trees). Let $C$ be a cycle in $(V, S)$, traversed with some direction, and orient this traversal. For each edge $e \in C$, let $\epsilon_e = +1$ if the traversal direction of $C$ agrees with $e$'s orientation in $B$, and $\epsilon_e = -1$ otherwise. Then for every vertex $v$, $\sum_{e \in C} \epsilon_e B_{ve} = 0$: each vertex $v$ on the cycle has exactly one incoming and one outgoing cycle-edge under the traversal, and one checks directly that the signed contributions from these two incident edges cancel (the entry from the edge where the traversal agrees with orientation and the entry where it disagrees combine to $0$ regardless of the original head/tail assignment — a short case check on the four sign combinations confirms this), while vertices off the cycle contribute $0$ trivially as $B_{ve}=0$ for $e \notin C$ incident-free entries. Hence the columns of $B_S$ indexed by $C$ satisfy a nontrivial linear dependency $\sum_{e \in C}\epsilon_e (\text{column } e) = 0$, so $B_S$ (and hence $B^{(i)}_S$, its submatrix with row $i$ removed) has linearly dependent columns, giving $\det(B^{(i)}_S) = 0$. Case B: $(V,S)$ is a spanning tree $T_S$. We show $\det(B^{(i)}_S) = \pm 1$ by induction on $n$. If $n = 2$: $T_S$ is a single edge, $B^{(i)}_S$ is a $1\times 1$ matrix with entry $\pm 1$ (the incidence sign at the surviving vertex), so $\det = \pm1$. For $n > 2$: since $T_S$ is a tree on $n \ge 2$ vertices it has a leaf $\ell$. Two subcases:

• If $\ell \ne i$: the row of $B_S$ corresponding to $\ell$ has exactly one nonzero entry, $\pm 1$, in the column for the unique edge $e_0$ at $\ell$ (all other columns have a $0$ in row $\ell$, since $\ell$ is incident to only $e_0$). Expanding $\det(B^{(i)}_S)$ along the row $\ell$ (present in $B^{(i)}_S$ since $\ell \ne i$) gives $\det(B^{(i)}_S) = \pm 1 \cdot \det\big((B^{(i)}_S)$ with row $\ell$, column $e_0$ deleted$\big)$, up to sign. The remaining matrix is exactly the analogous incidence submatrix for the spanning tree $T_S - \ell$ of $G - \ell$ on $n - 1$ vertices (with the same reference row $i$ deleted, since $i \ne \ell$), which by the inductive hypothesis has determinant $\pm 1$. Hence $\det(B^{(i)}_S) = \pm 1$.
• If $\ell = i$: then row $i$, which is deleted to form $B^{(i)}$, was the only row with a nonzero entry in column $e_0$ (the edge at leaf $i$). So in $B^{(i)}_S$, column $e_0$ is entirely zero — wait, we must instead argue directly: since $i=\ell$ is a leaf incident only to edge $e_0$, and row $i$ is removed, the remaining $n-1$ rows of $B_S$ restricted to the other $n-2$ vertices and $n-2$ edges (deleting column $e_0$ as well, which is now handled by observing that in $B^{(i)}_S$ every other row has its usual entries) reduce, after expanding along column $e_0$ (which in $B^{(i)}_S$ has exactly one nonzero entry, $\pm1$, in the row of $\ell$'s tree-neighbor — since $\ell$'s only edge is $e_0$ and the row for $\ell$ itself is absent, but $e_0$'s other endpoint, say $j\ne i$, still has a $\pm1$ in column $e_0$ and no other column of $e_0$'s row overlaps since $j$ may have other edges too, so instead we expand along column $e_0$, which has a unique nonzero entry precisely at row $j$ if $j$'s only shared edge with this column is $e_0$, true since each column of an incidence matrix has exactly two nonzero entries total, one per endpoint, and one of those endpoints is $i$ whose row is deleted) — we get $\det(B^{(i)}_S) = \pm 1 \cdot \det(\text{submatrix for } T_S - \ell \text{ on } G-\ell, \text{ row } j \text{ or appropriate new reference deleted})$, which by the inductive hypothesis (applied with $j$ or any fixed vertex of the smaller tree as reference row, all being equal by the symmetry we are in the process of establishing, or directly by re-deriving the $n-1$ case with reference vertex $j$) is $\pm 1$.

In both subcases $\det(B^{(i)}_S) = \pm 1$, completing the induction.

Step 5: Conclusion. Combining Steps 3 and 4:

This holds for every choice of reference vertex $i$, so in particular all cofactors $\det(L^{(i)})$ are equal to the same number $\tau(G)$, independent of $i$. $\blacksquare$

For $G = K_n$, $L = nI_n - J_n$, where $J_n$ is the all-ones matrix. Delete row $n$ and column $n$ to get the $(n-1)\times(n-1)$ matrix $L^{(n)} = nI_{n-1} - J_{n-1}$. The matrix $J_{n-1}$ has eigenvalues $n-1$ (once, eigenvector $\mathbf{1}$) and $0$ (with multiplicity $n-2$, on the orthogonal complement of $\mathbf 1$ inside $\mathbb R^{n-1}$). Hence $nI_{n-1} - J_{n-1}$ has eigenvalues $n - (n-1) = 1$ (once) and $n - 0 = n$ (multiplicity $n-2$). Its determinant, as the product of eigenvalues (valid since a real symmetric matrix is diagonalizable and determinant is the product of eigenvalues counted with multiplicity), is

By the Matrix-Tree Theorem, $\tau(K_n) = \det L^{(n)} = n^{n-2}$, matching Cayley's formula since every labeled tree on $[n]$ is (trivially) a spanning tree of $K_n$, and conversely. $\blacksquare$