Definition 1. Let $T_n$ denote the set of labeled trees on vertex set $\left[n\right]=\{1,2,\dots ,n\}$. Let $P_{n-2}$ denote the set of sequences $(a_1,a_2,\dots ,a_{n-2})$ where $a_i\in \left[n\right]$ for all $i$.

Theorem. There exists a bijection $\varphi :T_n\to P_{n-2}$.

Construction of $\varphi$ (Tree to Prüfer sequence):

Given $T\in T_n$, define $\varphi \left(T\right)=(a_1,a_2,\dots ,a_{n-2})$ by the following algorithm:

For $i=1,2,\dots ,n-2$:

• Let $v_i$ be the leaf with minimum label in the current tree
• Let $a_i$ be the unique neighbor of $v_i$
• Remove $v_i$ from the tree

Construction of ${\varphi }^{-1}$ (Prüfer sequence to tree):

Given $(a_1,a_2,\dots ,a_{n-2})\in P_{n-2}$, construct $T$ as follows:

• Define degree sequence: $\text{deg}\left(v\right)=1+\left|\right\{i:a_i=v\left\}\right|$ for all $v\in \left[n\right]$
• For $i=1,2,\dots ,n-2$:
  • Let $v_i$ be the minimum element with $\text{deg}\left(v_i\right)=1$
  • Add edge $\{v_i,a_i\}$ to $T$
  • Set $\text{deg}\left(v_i\right)\leftarrow \text{deg}\left(v_i\right)-1$ and $\text{deg}\left(a_i\right)\leftarrow \text{deg}\left(a_i\right)-1$
• Add edge between the two remaining vertices with degree 1

Proof of Bijectivity:

Lemma 1. The forward construction is well-defined.

Proof: At each step, exactly one leaf exists with minimum label since we have a tree with $\ge 2$ vertices.

Lemma 2. The reverse construction produces a tree.

Proof: The degree sequence satisfies $\sum _{v=1}^n\text{deg}\left(v\right)=2(n-1)$. At each step, exactly one vertex has degree 1 and is minimal. The final graph is connected with $n-1$ edges, hence is a tree.

Lemma 3. ${\varphi }^{-1}\left(\varphi \right(T\left)\right)=T$ for all $T\in T_n$.

Proof: Let $(a_1,\dots ,a_{n-2})=\varphi \left(T\right)$. In the forward construction, vertex $v_i$ (the $i$-th leaf removed) has degree 1 in the initial tree. In the reverse construction with sequence $(a_1,\dots ,a_{n-2})$, we have $\text{deg}\left(v_i\right)=1$ initially, and $v_i$ is chosen at step $i$ since it's the minimal vertex with degree 1. The edge $\{v_i,a_i\}$ added in reverse construction matches the edge removed in forward construction.

Lemma 4. $\varphi \left({\varphi }^{-1}\right(S\left)\right)=S$ for all $S\in P_{n-2}$.

Proof: Let $T={\varphi }^{-1}\left(S\right)$ where $S=(a_1,\dots ,a_{n-2})$. By construction of $T$, at step $i$ of computing $\varphi \left(T\right)$, the minimum leaf is $v_i$ (the vertex chosen at step $i$ in reverse construction), and its neighbor is $a_i$.

Corollary. $\varphi$ establishes the bijection.

Since $`\varphi \circ {\varphi }^{-1}={\text{id}}_{P_{n-2}}`$ and $`{\varphi }^{-1}\circ \varphi ={\text{id}}_{T_n}`$, we have $`\varphi :T_n\to P_{n-2}`$ is bijective.