Изменения

1. Вершина <tex>n</tex> не удаляется, так как у неё максимальный номер (в графе с <tex>>1</tex> вершиной - <tex>\leq geq 2</tex> листа), а, значит, на последнем шаге у неё была смежная вершина. <tex>\Rightarrow</tex> <tex> n </tex> - как минимум один раз встретилось в коде. 2. Если вершина, - не лист, то у неё на каком-то шаге была смежная вершина - лист. А, значит, номер этой вершины был <tex>>1</tex> выписан в код. 3. Так как вершина - лист(с номером не равным <tex>n</tex>), она была только удалена.

А, значит, все вершины, не являющиеся листьями "входят" в код Прюфера, а являющиеся листьями - "не входят".

Выберем минимальное число <tex>v</tex> не лежащее в A. Это означает, что <tex>v</tex> - вершина, которую мы удалили первой(По предыдущей лемме v - лист, а по построению кода мы удаляем вершину лист с минимальным номером). А, значит, это лист. Соединяем <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> - <tex>a_1</tex>. Далее будем перенумеровывать вершины, то есть - <tex>\forall i : a_i > v</tex> выполняем <tex>a_i = a_i - 1</tex>. А теперь мы можем применить предположение индукции.