Принцип крайнего

Обозначим висячие вершины Для каждой пары висячих вершин и существует единственный путь между ними. Назовём количество рёбер на этом пути расстоянием между этими вершинами и будем обозначать его через Из конечности числа способов разбить эти вершин на пар следует, что при одном из способов достигается максимум суммы расстояний между вершинами в парах. Соединим пары вершин при этом разбиении новыми рёбрами (остальные рёбра будем называть старыми). Мы докажем, что после этого даже при удалении любого ребра сохраняется связность графа.

Предположим противное, пусть при удалении ребра между вершинами и граф распался на две компоненты. Ясно, что удалённое ребро было старым, а вершины и принадлежат разным компонентам. В каждой части должна быть вершина, из которой выходит ровно одно старое ребро: в исходном графе обе компоненты связности являются деревьями, а любое дерево содержит хотя бы две висячие вершины. Также отметим, что каждое новое ребро соединяет две вершины из одной части. Но тогда в одной из частей должно быть новое ребро, соединяющее вершины и а в другой – соединяющее вершины и

Далее будем рассматривать пути в исходном графе. Напомним, что так как исходный граф – дерево, между любыми двумя вершинами в нем существует единственный путь. Пути и соединяющие соответственно с и с должны содержать ребро Следовательно, путь из в состоит из участка пути соединяющего с и участка пути соединяющего с Аналогично путь из в проходит через точку Таким образом, Это значит, что если удалить ребра и добавить ребра , то сумма расстояний между вершинами парах увеличится, что противоречит максимальности выбранного способа соединения вершин.