Задача
COM-B2-M04-P004 Лист в дереве
#4
★★☆☆☆ Уровень 2 из 5
Докажите, что в любом конечном дереве с хотя бы двумя вершинами найдётся вершина степени \(1\).
Возьмите самый длинный простой путь в дереве.
Выберем в дереве путь максимальной длины \(v_1v_2\ldots v_k\). Если у вершины \(v_k\) есть сосед, не лежащий на пути, путь можно продолжить, что невозможно.
Если \(v_k\) соединена с какой-то более ранней вершиной пути, кроме \(v_{k-1}\), то возникнет цикл. В дереве циклов нет. Значит, единственный сосед \(v_k\) — это \(v_{k-1}\), и степень \(v_k\) равна \(1\).
Задача показывает, как экстремальный путь даёт структурное свойство дерева.