Задача
COM-B2-M04-P020 Два самых длинных пути
Докажите, что в любом конечном связном графе любые два пути максимальной длины имеют хотя бы одну общую вершину.
Предположите, что два самых длинных пути не пересекаются, и соедините их кратчайшим путём.
Пусть два пути максимальной длины \(P\) и \(Q\) не имеют общих вершин. Обозначим их длину через \(L\). Так как граф связен, существует путь, соединяющий некоторую вершину \(x\) пути \(P\) с некоторой вершиной \(y\) пути \(Q\). Выберем такой соединяющий путь кратчайшим; тогда его внутренняя часть не пересекает \(P\) и \(Q\).
Вершина \(x\) делит путь \(P\) на две части, суммы длин которых равна \(L\). Одна из этих частей имеет длину не меньше \(\frac{L}{2}\). Аналогично, вершина \(y\) делит путь \(Q\) на две части, и одна часть имеет длину не меньше \(\frac{L}{2}\).
Возьмём более длинную часть пути \(P\), затем соединяющий путь от \(x\) к \(y\), затем более длинную часть пути \(Q\). Получается простой путь: внутренние вершины соединяющего пути не лежат на \(P\) и \(Q\), а сами \(P\) и \(Q\) не пересекаются.
Его длина не меньше \(\frac{L}{2}+1+\frac{L}{2}=L+1\), потому что соединяющий путь имеет положительную длину. Это больше максимальной длины \(L\), противоречие. Следовательно, два самых длинных пути должны иметь общую вершину.
Сильная задача на экстремальный принцип: нужно выбрать кратчайший мост между двумя экстремальными объектами.