Задача
COM-B1-M09-P016 Два листа
#16
★★★☆☆ Уровень 3 из 5
Докажите, что в любом дереве с хотя бы двумя вершинами есть не менее двух вершин степени \(1\).
Возьмите самый длинный простой путь.
Рассмотрим самый длинный простой путь в дереве. Пусть его конец - вершина \(v\). Если у \(v\) есть сосед, не лежащий на пути, путь можно продолжить, противоречие. Если у \(v\) есть сосед на пути кроме ближайшего, возникнет цикл, что невозможно в дереве. Значит у \(v\) ровно один сосед, степень \(1\). То же верно для другого конца пути.
Классический прием «самый длинный путь».