Изменения
→Число вершин
Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше числа листьев.
|proof=
: '''Переход''' <tex>n \rightarrow n + 1</tex> : Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка {{---}} листья. Рассмотрим возможные случаи:
# У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем число внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма верна.
