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

Рассмотрим граф, в котором вершины — города, рёбра — дороги. Предположим противное. Пусть нашлись два города и такие, что от после удаления ребра нельзя добраться по двум дорогам до Дорогу из города в город будем обозначать

Возможны всего три случая: закрыли прямую дорогу на пути закрыли дорогу на пути закрыли дорогу

Разберём первый случай: закрыли прямую дорогу В графе после удаления ребра найдется путь между и пусть это дорога

В исходном графе был путь от до проходящий не более, чем по двум дорогам. Заметим, что этот путь не мог проходить через закрытое ребро, иначе дорога между и была бы двусторонней — противоречие. Тогда можно по двум дорогам проехать из в а оттуда напрямую в

Разберёмся со вторым случаем: на закрыли дорогу В графе после удаления ребра есть какая-то дорога от до пусть это дорога

В исходном графе был путь из в Заметим, что этот путь не мог проходить через удаленное ребро, ведь это ребро не может быть ни первым в пути, ни последним, а ребер всего два. Тогда можно пройти из в а потом по этому пути.

Третий случай: на закрыли дорогу В графе после удаления ребра есть какая-то дорога от до пусть это дорога

В исходном графе был путь от до проходящий не более, чем по двум дорогам. Заметим, что этот путь не мог проходить через закрытое ребро, ведь это ребро не может быть ни первым, ни вторым в пути. Тогда можно пройти по этому пути, после чего завершить маршрут ребром