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

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