Некоторые из городов страны соединены дорогами; из каждого города выходит не более трех дорог. Докажите, что все города можно разбить на две группы так, чтобы не более трети дорог соединяли города из одной группы.
Подсказка
Допустим, что каждый город соединен не более чем с двумя другими. Тогда все дороги объединяются в циклы (замкнутые маршруты) и цепи (незамкнутые маршруты), не связанные между собой.
Решение
Допустим, что каждый город соединен не более чем с двумя другими. Тогда все дороги объединяются в циклы (замкнутые маршруты) и цепи (незамкнутые маршруты), не связанные между собой. В каждой цепи и каждом цикле четной длины отметим города красным и синим цветами так, чтобы цвета чередовались, а в каждом цикле нечетной длины отметим красным какие-либо два соседних города, а остальные снова покрасим так, чтобы их цвета чередовались. Тогда синие города вообще не будут связаны дорогами, а дорог, соединяющих красные, будет столько же, сколько циклов нечетной длины. Поскольку в каждом нечетном цикле не меньше трех дорог, дорог, соединяющих одноцветные города, будет не больше трети от общего числа дорог.
В общем случае будем удалять по одному города, из которых выходит по три дороги, вместе с выходящими из них дорогами до тех пор, пока не окажется, что каждый из оставшихся городов соединен не более чем с двумя другими. Затем раскрасим оставшиеся города так, как сказано выше, а после будем по одному добавлять удаленные города и красить каждый добавленный город в синий цвет, если хотя бы две дороги из него ведут в красные города, и в красный в противном случае. Легко понять, что разбиение городов на красные и синие, которое мы получим в итоге, удовлетворяет условию задачи.