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

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

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

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

For $i = 1,2,\ldots,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 $\phi^{-1}$ (Prüfer sequence to tree):**

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

- Define degree sequence: $\text{deg}(v) = 1 + |\{i : a_i = v\}|$ for all $v \in [n]$
- For $i = 1,2,\ldots,n-2$:
  - Let $v_i$ be the minimum element with $\text{deg}(v_i) = 1$
  - Add edge $\{v_i, a_i\}$ to $T$
  - Set $\text{deg}(v_i) \leftarrow \text{deg}(v_i) - 1$ and $\text{deg}(a_i) \leftarrow \text{deg}(a_i) - 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 $\geq 2$ vertices.

**Lemma 2.** The reverse construction produces a tree.

*Proof:* The degree sequence satisfies $\sum_{v=1}^n \text{deg}(v) = 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.** $\phi^{-1}(\phi(T)) = T$ for all $T \in T_n$.

*Proof:* Let $(a_1,\ldots,a_{n-2}) = \phi(T)$. 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,\ldots,a_{n-2})$, we have $\text{deg}(v_i) = 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.** $\phi(\phi^{-1}(S)) = S$ for all $S \in P_{n-2}$.

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

**Corollary.** $\phi$ establishes the bijection.

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