80
правок
Изменения
→Количество вершин
Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка - листья. Рассмотрим возможные случаи:
1) У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин (т.к. по индукционному предположению для него выполняется условие леммы), значит, для исходного дерева лемма верна.
2) У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n</tex> листьями, количество внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда, по индукционному предположению, у него менее <tex>n</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n + 1</tex>.
}}
