FormulaProved

Cayley's formula for labeled trees

Statement

For any integer $n \ge 1$ , the number of trees on $n$ labeled vertices $\{1,\dots,n\}$ is $n^{n-2}$ (with $1^{-1}=1$ for $n=1$ ).

Why is it true?

Every labeled tree on $n$ vertices can be encoded uniquely as a sequence of $n-2$ vertex labels (its Prüfer code) by repeatedly plucking the smallest-numbered leaf and recording its neighbor; conversely, any such sequence of length $n-2$ from $\{1,\dots,n\}$ decodes to a unique tree, so there are $n^{n-2}$ of them.

Proof sketch

Construct Prüfer's bijection between labeled trees on $\{1,\dots,n\}$ and sequences in $\{1,\dots,n\}^{n-2}$ : at each of $n-2$ steps, delete the leaf with the smallest label and append its unique neighbor's label to the sequence, leaving a single edge at the end. Observe that a vertex $v$ appears in the Prüfer sequence exactly $\deg(v)-1$ times, so the leaves of the original tree are the labels absent from the sequence, which makes each step uniquely reversible and establishes the bijection.

Topics that use this theorem

Trees

Related theorems

Handshaking lemma

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Arthur Cayley (1889). A theorem on trees