For a labelled graph, if the vertex appear $k-1$ times in the Prüfer sequence of the graph, then the vertex has degree $k$
My thought was to prove this by induction on $n$, the number of vertices of the graph.
The base case is $n=2$, which means both vertices are leaves, so the Prüfer sequence is empty and the claim holds.
How should I proceed on the inductive case? Thanks for any help.
When you remove the first leaf $v$ of tree $T$ you write the number of its neighbor $u$ into the code and continue with a tree $T'$ on $n - 1$ vertices. Degrees of all vertices except $u$ and $v$ didn't change while degrees of $u$ and $v$ decreased by $1$ (and therefore $v$ was excluded from tree). Note that vertex $u$ wasn't leaf if $n \ge 3$. The induction hypothesis tells that each vertex of degree $d$ of tree $T'$ will appear $d - 1$ times in Prüfer code. So for each vertex $w$ of $T$ other than $v$ and $u$ it appeared $\deg_T w - 1$ times, that's what we need. Vertex $u$ appeared in code of $T$ exactly $(\deg_{T'} v - 1) + 1 = (\deg_T w - 2) + 1 = \deg_T w - 1$ times. Vertex $v$ couldn't appear in the code and $\deg_T v = 1$. So the induction step is proven.