Гуляем по графу

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