Олимпиадная задача по теории графов: разделение страны на губернии, 9-11 класс

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

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

  Предположим, что на этом пути есть городZ, лежащий в автономной области. Тогда изXможно добраться доZдвумя несамопересекающимися путями: один путь идёт черезY, а второй идёт только по городам области (такой путь существует, потому что для области выполнено условие задачи, как и для всей страны). Но это противоречит условию. Следовательно, путь изYвXне содержит других городов из области, кромеX.   Теперь присоединим все города на этом пути (включаяY) к автономной области и отнесём их поочерёдно в те две губернии, в которыеXне входит. Все дороги, соединяющие два присоединённых города, - это дороги на пути  Y→X,  иначе между ними было бы два пути. Аналогично все дороги, соединяющие присоединённый город с городом, уже имевшимся в области – это дорога изXвYи последняя дорога на пути  Y→X.  Следовательно, область будет правильно разделена на губернии.   Два несамопересекающихся пути от одного города к другому по области невозможны, иначе бы вся страна не удовлетворяла условию. От каждого города области можно доехать (по области) доX, а отX– до всех остальных, поэтому по крайней мере один путь от одного города области до другого всегда существует. Значит, новая область тоже удовлетворяет условию.   На каждом описанном шаге область увеличивается хотя бы на один город (Y). Следовательно, рано или поздно все города будут присоединены. В этот момент область совпадёт со всей страной и при этом будет разделена на губернии.

Ответ задачи отсутствует