Prüfer sequences

Encoding. Given a tree $T$ on $\{1,\ldots,n\}$:
1. Find the smallest leaf (degree $1$).
2. Record its unique neighbor.
3. Remove the leaf.
4. Repeat $n-2$ times; the sequence of recorded neighbors is the Prüfer sequence.

Decoding. Given a sequence of length $n-2$, reconstruct the tree.

Bijection. Prüfer sequences of length $n-2$ over $\{1,\ldots,n\}$ biject with labeled trees on $n$ vertices, giving $n^{n-2}$ trees.

Conclusion. Prüfer sequences give a bijective proof of Cayley's formula.