Задача
COM-B2-M04-P017 Две самые далёкие вершины дерева
#17
★★★★☆ Уровень 4 из 5
В дереве выбраны две вершины \(A\) и \(B\), расстояние между которыми максимально возможно. Докажите, что обе эти вершины являются листьями.
Если у \(A\) есть сосед не на пути от \(A\) к \(B\), расстояние можно увеличить.
Рассмотрим единственный путь от \(A\) к \(B\). Если степень \(A\) больше \(1\), то у \(A\) есть сосед \(C\), отличный от следующей вершины на пути к \(B\).
В дереве путь от \(C\) к \(B\) проходит через \(A\), поэтому расстояние \(CB\) на \(1\) больше расстояния \(AB\). Это противоречит максимальному выбору пары \(A,B\). Значит, степень \(A\) равна \(1\). Аналогично степень \(B\) равна \(1\).
Удобная подготовка к диаметру дерева.