Proof of Cayley's formula by Prüfer sequences

Proof

We show that the Prüfer sequence is a bijection, by induction on the number of vertices. For the induction we allow any finite set of integers as vertex set.

1. For a finite set $S \subseteq \Z$ with $\abs{S} = n \ge 2$, let $\mathcal{T}_S$ be the set of trees with vertex set $S$. Let $\mathcal{W}_S = S^{n-2}$ be the set of sequences of length $n - 2$ with entries in $S$.
2. Lemma A: if $T$ is a tree with at least two vertices and $\ell$ is a leaf, then $T - \ell$ is a tree. Here $T - \ell$ removes $\ell$ and its edge.
3. Proof of Lemma A. A cycle of $T - \ell$ would be a cycle of $T$, so $T - \ell$ is acyclic. It has the vertex adjacent to $\ell$.
4. Let $x, y \ne \ell$. By every walk contains a path, $T$ has a path from $x$ to $y$. An inner vertex of a path has two distinct neighbours on it, so $\ell$ is not on this path.
5. So the path lies in $T - \ell$, and $T - \ell$ is connected. This proves Lemma A.
6. Define $\pi(T) \in \mathcal{W}_S$ for $T \in \mathcal{T}_S$ by recursion on $n$. If $n = 2$, let $\pi(T)$ be the empty sequence.
7. If $n \ge 3$, let $\ell$ be the smallest leaf of $T$, which exists by the leaf lemma, and let $a$ be its neighbour. Let $\pi(T) = (a, \pi(T - \ell))$, using Lemma A.
8. Unwinding the recursion gives exactly the process that defines the Prüfer sequence. So for $S = \set{1, \dots, n}$, $\pi(T)$ is the Prüfer sequence of $T$.
9. Lemma B: each vertex $x$ of $T \in \mathcal{T}_S$ appears exactly $\deg(x) - 1$ times in $\pi(T)$. We prove it by induction on $n$.
10. If $n = 2$, $T$ has one edge, both vertices have degree $1$, and $\pi(T)$ is empty.
11. Let $n \ge 3$, with $\ell, a$ as in step 7 and $T' = T - \ell$. The vertex $\ell$ has degree $1$, and it does not appear in $\pi(T)$, since $a \ne \ell$ and $\ell$ is not a vertex of $T'$.
12. The vertex $a$ appears $1 + (\deg_{T'}(a) - 1) = \deg_T(a) - 1$ times, by the induction hypothesis. Every other vertex $x$ has $\deg_{T'}(x) = \deg_T(x)$, and appears $\deg_T(x) - 1$ times.
13. Consequence of Lemma B: every vertex of $T$ has degree at least $1$, since $T$ is connected with $n \ge 2$ vertices. So the leaves of $T$ are exactly the elements of $S$ that do not appear in $\pi(T)$.
14. Claim: for every $S$ with $\abs{S} = n \ge 2$, the map $\pi : \mathcal{T}_S \to \mathcal{W}_S$ is a bijection. We argue by induction on $n$.
15. If $n = 2$, say $S = \set{a, b}$, the only tree on $S$ has the single edge $ab$, because the graph with no edge is not connected. And $\mathcal{W}_S$ has only the empty sequence.
16. Let $\abs{S} = n + 1 \ge 3$, and assume the claim for all sets of size $n$. Let $w = (w_1, \dots, w_{n-1}) \in \mathcal{W}_S$.
17. The sequence $w$ has at most $n - 1$ distinct entries, and $S$ has $n + 1$ elements. Let $\ell$ be the smallest element of $S$ that does not appear in $w$.
18. Let $S' = S \setminus \set{\ell}$ and $w' = (w_2, \dots, w_{n-1})$. Then $w' \in \mathcal{W}_{S'}$. By the induction hypothesis, there is exactly one $T' \in \mathcal{T}_{S'}$ with $\pi(T') = w'$.
19. Existence. Let $T$ be $T'$ with the new vertex $\ell$ and the new edge $\ell w_1$; note $w_1 \in S'$. Then $T$ is connected, since $T'$ is connected and $\ell$ is joined to $w_1$.
20. A cycle in $T$ through $\ell$ would give $\ell$ two distinct neighbours, but $\ell$ has degree $1$. A cycle avoiding $\ell$ would lie in $T'$. So $T$ is acyclic, and $T \in \mathcal{T}_S$.
21. The vertex $w_1$ has degree at least $2$ in $T$: one edge in $T'$ by step 13, and the edge to $\ell$. So $w_1$ is not a leaf of $T$.
22. Let $x \ne \ell, w_1$ be a leaf of $T$. Then $x$ is a leaf of $T'$, so $x$ does not appear in $w'$ by step 13. Also $x \ne w_1$, so $x$ does not appear in $w$.
23. By the choice of $\ell$ in step 17, $x > \ell$. So $\ell$ is the smallest leaf of $T$, with neighbour $w_1$, and $T - \ell = T'$.
24. By step 7, $\pi(T) = (w_1, \pi(T')) = (w_1, w') = w$.
25. Uniqueness. Let $Q \in \mathcal{T}_S$ with $\pi(Q) = w$. By step 13, the leaves of $Q$ are the elements of $S$ not in $w$. The smallest of them is $\ell$.
26. By step 7, the neighbour of $\ell$ in $Q$ is $w_1$, and $\pi(Q - \ell) = w'$. By Lemma A, $Q - \ell \in \mathcal{T}_{S'}$. By step 18, $Q - \ell = T'$.
27. So the edges of $Q$ are those of $T'$ together with $\ell w_1$. These are the edges of $T$, so $Q = T$. This proves the claim.
28. Take $S = \set{1, \dots, n}$. By the number of functions between finite sets, $\abs{\mathcal{W}_S} = n^{n-2}$.
29. By the claim and the bijection principle, the number of trees with vertex set $\set{1, \dots, n}$ is $n^{n-2}$.