Cayley's Formula

From ProofWiki
Jump to navigation Jump to search

This proof is about Cayley's Formula in the context of Graph Theory. For other uses, see Cayley's Theorem.

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:

$\tuple {\mathbf a_1, \mathbf a_2, \ldots, \mathbf a_{n - 2} }$

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 $\ds \prod_{i \mathop = 1}^{n - 2} n$.

The result follows from Equivalence of Mappings between Finite Sets of Same Cardinality.

$\blacksquare$


Source of Name

This entry was named for Arthur Cayley.


Historical Note

Arthur Cayley 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 cannot be generalized to larger $n$.

The proof given here, the work of Heinz Prüfer, first appeared in $1918$.


Sources