Cayley's Formula

Theorem

The number of distinct labeled trees with $n$ nodes is $n^{n-2}$.

Proof

Follows directly from Bijection between Prüfer Sequences and Labeled Trees.

This shows that there is a bijection between the set of labeled trees with $n$ nodes and the set of all Prüfer sequences of the form:

$\left({\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_{n-2}}\right)$

where each of the $\mathbf{a}_i$'s is one of the integers $1, 2, \ldots, n$, allowing for repetition.

Since there are exactly $n$ possible values for each integer $\mathbf{a}_i$, the total number of such sequences is $\displaystyle \prod_{i=1}^{n-2} n$.

The result follows from Same Cardinality Bijective Injective Surjective.

$\blacksquare$

Source of Name

This entry was named for Arthur Cayley.

Historical Note

This proof, given by Heinz Prüfer, first appeared in 1918.

Cayley himself first stated this theorem in his A Theorem on Trees in 1889, but his proof was unsatisfactory as he discussed only the case where $n=6$, and his method can not be generalized to larger $n$.