Cayley's formula

Fix the vertex set $\{1,\dots,n\}$ and, for $n\ge2$, define the Prüfer sequence of a labeled tree $T$: repeatedly find the leaf with the smallest label, write down the label of its unique neighbor, and delete that leaf; stop once $2$ vertices remain. This records $n-2$ labels (one per deletion, since we start with $n$ vertices and stop at $2$), so every labeled tree produces a sequence in $\{1,\dots,n\}^{n-2}$.

There are exactly $n^{n-2}$ such sequences, since each of the $n-2$ positions is independently any of the $n$ labels. It remains to show this encoding is a bijection, so that labeled trees are in exact one-to-one correspondence with these sequences.

The key fact is that in the Prüfer sequence, label $i$ appears exactly $\deg(i)-1$ times: every time one of $i$'s neighbors is deleted as a leaf, $i$ is written down once, and $i$ itself is only ever deleted (contributing no writes) once all but one of its incident edges are gone. In particular, the labels that never appear in the sequence are exactly the original leaves. This lets us decode: given a sequence $(a_1,\dots,a_{n-2})$, repeatedly take the smallest label not currently used as a remaining sequence entry or already attached, join it by an edge to the first remaining sequence entry, remove that label from further consideration and remove that entry from the sequence; after all $n-2$ entries are consumed, join the $2$ labels left over by a final edge.

This decoding procedure exactly reverses the encoding step by step — at each stage it identifies the same smallest-label leaf and the same neighbor that the encoder would have recorded, by induction on the number of vertices remaining. So encoding and decoding are mutually inverse, giving a bijection between labeled trees on $n$ vertices and sequences in $\{1,\dots,n\}^{n-2}$. Since there are $n^{n-2}$ such sequences, there are exactly $n^{n-2}$ labeled trees on $n$ vertices.