Задача
COM-B2-M07-P003 Лист в дереве
#3
★★☆☆☆ Уровень 2 из 5
Докажите, что в любом дереве с хотя бы двумя вершинами есть как минимум два листа.
Возьмите самый длинный путь.
Выберем самый длинный простой путь в дереве. Если у его конечной вершины есть сосед вне пути, путь можно продолжить. Если она соединена с другой вершиной пути, кроме соседней, возникнет цикл. Значит, её степень равна \(1\). То же верно для другого конца пути. Получаем два листа.
Это stronger version базового факта о листе.