Let $(a_1, \dots, a_{n-2})$ be a sequence of integers with $1 \leq a_i \leq n$. Prove that $(a_1, \dots, a_{n-2})$ is the Prufer sequence of some tree with vertex set $\{1, \dots, n\}$.
The proof is a proof by induction, and is as follows: Let $k$ be the smallest integer in $\{1, \dots, n\}$ that does not appear in $(a_1, \dots, a_{n-2})$. Then by the inductive hypothesis, $(a_2, \dots, a_{n-2})$ is a Prüfer sequence of a tree with vertex set $\{1, \dots, k-1, k+1, \dots, n\}$. We form a tree $T$ by adding the vertex $k$ and connecting it to $a_1$. Then $T$ has Prufer sequence $(a_1, \dots, a_{n-2})$.
I'm confused about a few things about this proof:
If $n$ appears in $(a_2, \dots, a_{n-2})$, then we cannot apply the inductive hypothesis as there would be a restriction on $a_i \leq n-1$. How does this work?
When applying the inductive hypothesis, doesn't the vertex set of the generated tree need to be of form $(1, \dots, n-1)$? Why can we arbitrarily choose its vertex set to be $\{1, \dots, k-1, k+1, \dots, n\}$?
Any help would be appreciated!
What you're asking for is the decoding of a Prüfer sequence.
I'm going to describe this decoding on one example: start with the Prüfer sequence $P=(5,2,1,6)$ (hence on vertex-set $V=\{1,2,3,4,5,6\}$).
We are going to construct the edge list $T$ of the corresponding tree.
The least number appearing in $V$ but not in $P$ is $3$, so we add the edge $\{3,5\}$ to $T$, and remove $5$ from $P$ and $3$ from $V$. $T$ is currently $\{ \{3,5\} \}$.
We now have $P=(2,1,6)$ (hence on vertex-set $V=\{1,2,4,5,6\}$. The least number appearing in $V$ but not in $P$ is $4$, so we add the edge $\{4,2\}$ to $T$, and remove $2$ from $P$ and $5$ from $V$. $T$ is now $\{ \{3,5\};\{2,4\} \}$.
We now have $P=(1,6)$ and remaning vertices are $V=\{1,2,5,6\}$. The least number appearing in $V$ but not in $P$ is $2$, so we add the edge $\{2,1\}$ to $T$, and remove $1$ from $P$ and $2$ from $V$. $T$ is now $\{ \{3,5\};\{2,4\} ; \{1,4\} \}$.
Now $P=(6)$ a nd $V=\{1,5,6\}$. The least number appearing in $V$ but not in $P$ is $1$, so we add the edge $\{1,6\}$ to $T$, and remove $6$ from $P$ and $1$ from $V$. $T$ is now $\{ \{3,5\};\{2,4\} ; \{1,4\} ; \{1,6\} \}$.
Now $P$ is empty, and vertices $5$ and $6$ are left in $V$, so we add the edge $\{5,6\}$ to $T$, which is finally full (size $6-1 = 5$) and equal to $\{ \{3,5\};\{2,4\} ; \{1,4\} ; \{1,6\} ; \{5,6\} \}$.
This can be used to show that Prüfer encoding is a bijection from trees with $n$ vertices to sequences in $\{1,...,n\}^{n-2}$ because:
1- from any sequence $P$ in $\{1,...,n\}^{n-2}$ you get a tree $T$ on $n$ vertices
2- the Prüfer sequence of $T$ is $P$ (we haven't quite proved this but is holds, you can test this on the example)