Все верно, но мне хотелось бы доказать для последовательности
![$[a_1,a_2, .. a_{n-2}, n]$ $[a_1,a_2, .. a_{n-2}, n]$](https://dxdy-02.korotkov.co.uk/f/d/c/b/dcb596f3f925654664f03cdf3383ed0b82.png)
(Именно ее назовем кодом Прюфера)
Если же мы соединим

и

ребром, и перенумеруем, то получим последовательность
![$[a_1'..a_{n-3}',n]$ $[a_1'..a_{n-3}',n]$](https://dxdy-04.korotkov.co.uk/f/b/2/b/b2be9a00b4507b6b0561b969b384555782.png)
и предположение индукции не применить.
Не вижу проблем с шагом: у вас изначально есть последовательность длины

чисел, лежащих в интервале от

до

, после удаления - последовательность чисел длины

чисел в интервале от

до

(Кстати,

на конце останется только в том случае, если

равнялось

, в противном случае оно превратится в

после перенумерации). Быть может, чтобы "порушить" доказательство, вы имели в виду последовательность
![$[a_1,a_2, ..., a_{n-2}, n + 1]$ $[a_1,a_2, ..., a_{n-2}, n + 1]$](https://dxdy-02.korotkov.co.uk/f/5/4/f/54fa24d055a1b62a668246c4e932d8e782.png)
, то есть с последней по номеру вершиной на конце (ну или вообще где-то в последовательности)? Но в таком случае любое (в том числе наименьшее)

, не принадлежащее последовательности и не большее

будет, очевидно, меньше

, и значит после соединения и перенумерации мы получим последовательность
![$[a_1', ..., a_{n - 3}', n]$ $[a_1', ..., a_{n - 3}', n]$](https://dxdy-02.korotkov.co.uk/f/9/3/1/931f13ba5875b142b15dfde8aeb92eb582.png)
, снова корректную: длиной на единицу меньше и с числами, не превосходящими

.