Раскраски графов

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