Изменения
Нет описания правки
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
1. Каждому помеченному дереву соотвествует последовательность и только одна - Верно . Это верно по построению кода.<br>2. Каждой последовательности соотвествует помеченное дерево и только одно - Верно . Это верно по предыдущей лемме, т.к. восстанавливали мы однозначно.<br>Значит, это биекция - по определению.
}}
Следствием из этой теоремы является [[Количество помеченных деревьев|теорема Кэли]].
