М1873. Граф, из любой вершины которого в любую другую путь единственный

В стране несколько городов, соединённых дорогами с односторонним или двусторонним движением. Из любого города в любой другой можно проехать ровно одним путём, не проходящим два раза ни через какой город. Докажите, что города можно так распределить между тремя губерниями, чтобы любая дорога соединяла города из разных губерний. Решение. Рассмотрим любой город. Будем добавлять к нему по несколько новых городов так, чтобы на каждом этапе было возможно распределение на три губернии и рассматриваемый подграф G удовлетворял условию задачи. Рассмотрим некоторый ещё не добавленный город A. Дойдём от него кратчайшим путём до G. Из города B, в который мы при этом пришли, существует и единственен путь P без повторяющихся городов, ведущий в A. Если бы пути P принадлежал отличный от B город C из G, то кроме проходящего только по G существовал бы ещё один путь из C в B (через A). Значит, пути из A в B и из B в A пересекаются с G только по городу B. Добавляя города этих путей к G, получаем подграф, который тоже удовлетворяет условию задачи и который тоже можно разбить на три губернии. LXVI московская олимпиада, журнал «Квант» 2004 года, номер 1. Это видео из альбома    • 2018-2022 Для старшеклассников. Спивак   Альбом «Задачник "Кванта"»    • Задачник "Кванта"   Условия и ссылки на решения: