This question is not unique and has been asked before (link). My question is here since:
- It is not about induction (or not only about induction)
- Answer in previous question, very unfortunately, wasn't informative for me. In general, it is a good hint, but I don't know how to use it, because I can't imagine proof.
You don't need induction; just analyze the algorithm that generates the Prüfer sequence. Whether vertex $i$ is removed during the algorithm or is one of the two vertices left over at the end of the algorithm, in either case $d_i − 1$ of its neigbours have been removed at that point, each resulting in an appearance of $i$ in the Prüfer sequence, and no further appearances of $i$ in the sequence will be generated afterwards.
So we have labeled graph $T$, vertices $v_i$, $i \in$ {$1, \cdots, n$}, $d_i$ -- degree of $v_i$
For me it is obvious that $v_i$ appears strictly $d_i - 1$ times in Prüfer code, because algorithm for building Prüfer code implies it. Vice versa, if we take any number of the Prüfer sequence and change it ($m + 1$ included), we will get another -- not origin -- graph.
But combinatorial proofs are somewhat "specific" as far as I know -- double counting proof and bijective proof. Can we somehow use it here? If yes, how so?