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