Эйлеровы графы

Пусть на ремонт закрыли дорогу из города в город .

По условию от любого города до другого существовал маршрут не более, чем из двух дорог. Если этот маршрут не содержал дорогу , то и после ремонта выполнено условие, что добраться данным маршрутом можно не более, чем по трём (даже двум) дорогам. Осталось рассмотреть маршруты вида , где - произвольный город, отличный от и .

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

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

В итоге путь имеет длину не больше трёх.