Простой путь, Гамильтонов путь, Гамильтонов цикл

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

Предположим, что область содержит не все города. Тогда найдётся дорога, ведущая из города области (обозначим его через в город, ещё не принадлежащий автономной области (назовём его Рассмотрим несамопересекающийся путь (последовательность дорог), ведущий из в

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

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

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

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