Изменения
→Коды Прюфера.
Номера всех вершин, которые не являются листьями или с номером <tex>n</tex>, встречаются в коде Прюфера. А те, которые не входят - являются листьями.
|proof=
1. Вершина <tex>n</tex> не удаляется, так как у неё максимальный номер (в графе с <tex>>1</tex> вершиной - <tex>\leq 2</tex> листа), а, значит, на последнем шаге у неё была смежная вершина. <tex>\Rightarrow</tex> n - как минимум один раз встретилось в коде.
2. Если вершина, не лист, то у неё на каком-то шаге была смежная вершина - лист. А, значит, номер этой вершины был <tex>>1</tex> выписан в код.
3. Так как вершина - лист(с номером не равным <tex>n</tex>), она была только удалена.
<br>
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</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>. А теперь мы можем применить предположение индукции.
}}
