Cayley's formula

Formula. $n^{n-2}$ labeled trees on $n$ labeled vertices.

Examples.
- $n=3$: $3^1=3$ trees (three possible edge sets).
- $n=4$: $4^2=16$ trees.
- $n=5$: $5^3=125$ trees.

Proof idea (Prüfer). A labeled tree corresponds to a Prüfer sequence of length $n-2$ over $\{1,\ldots,n\}$.

Conclusion. Cayley's formula: $n^{n-2}$ labeled trees on $n$ vertices.