The question is as below:
Show that each vertex $v$ of a tree $T$ appears $deg(v)-1$ times in the Prüfer encoding of $T$, where $deg(v)$ is the degree of $v$ in $T$.
For this, I think there are 3 scenarios a leaf should be considered for: (1) when it is a leaf as part of a tree; (2) a leaf that has been discarded; (3) the remaining edge. I feel like this will result in a short proof which is only two (or so) statements long, but at the same time, feel it is too simple.
EDIT: I've had a look at this again and narrowed it down to 2 cases:
Case 1: The vertex $v$ in question has $deg(v)\ge2$. $v$ then loses its neighbours as the algorithm is applied repeatedly until $v$ becomes a leaf itseelf. At this point, $v$ is attached to another neighbour, leaving an edge. This means the algorithm can no longer be applied and we have obtained the final Prüfer Encoding for the tree $T$.
Case 2: The vertex $v$ has $deg(v)\ge 2$. It loses its neighbours as the algorithm is applied repeatedly but is deleted itself at some point in the process.
Have I gone about this wrong?
Thank you.
Here's a proof by induction over the number of vertices. Denote the number of vertices by $n$.
Base case: $n=2$. Both vertices are leaves with degree 1, and the Prüfer code has length $0$, so both vertices appear $1-1=0$ times.
Induction step: Fix an $n>2$ to be the number of vertices. Assume that for all trees $T_k$ with $2\leq k<n$ vertices, all vertices $x$ appear in the Prüfer encoding of $T_k$ $deg(x)-1$ times.
Consider the lowest-numbered leaf, labeled $u$. It has degree $1$, and since it is the first to be deleted, it appears $deg(u)-1=1-1=0$ times in the Prüfer code. The vertex neighboring $u$, labeled $v$, then, has its label appear first in the Prüfer code of $T$.
Now that $u$ has been deleted, the part of the Prüfer code of $T$ following $v$ is just the Prüfer code of $T \setminus u$, where $T\setminus u$ is the tree remaining after $u$ and the edge connected to $u$ are removed.
We'll use $deg'$ to denote the degree of a vertex in $T \setminus u$, and $deg$ to denote the degree of a vertex in $T$.
$T \setminus u$ has less than $n$ vertices, so by our induction hypothesis, each vertex $x$ of $T \setminus u$ appears $deg'(x)-1$ times in the Prüfer code of $T \setminus u$.
For non-$v$ vertices $x$ in $T \setminus u$, $deg'(x)=deg(x)$, and so in the Prüfer code of $T$, each of these vertices $x$ appear $deg'(x)-1=deg(x)-1$ times. (Observe that the vertices in $T \setminus u$ that are not $v$ are the same as the vertices in $T$ that are neither $u$ nor $v$.)
Now, $deg'(v)=deg(v)-1$, since we have removed the edge between $u$ and $v$ to get from $T$ to $T \setminus u$. By the induction hypothesis, $v$ appears $deg'(v)-1=deg(v)-2$ times in the Prüfer code of $T \setminus u$. So $v$ appears as the first entry in the Prüfer code of $T$, as well as $deg(v)-2$ times in the rest of the Prüfer code of $T$, giving us $deg(v)-2+1=deg(v)-1$ total appearances of $v$ in the Prüfer code.
So putting everything together, we've shown that the number of times that $u$, $v$, and all vertices in $T$ that are neither $u$ nor $v$ appear in the Prüfer code of $T$ is one less than their degree.