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

Лемма. Пусть — средняя степень вершины в некотором графе (т.е. среднее арифметическое всех степеней его вершин). Тогда в этом графе можно удалить несколько вершин так, чтобы в оставшемся графе степень каждой вершины была не меньше

Доказательство. Индукция по количеству вершин. Для графа с одной вершиной утверждение очевидно ( Совершим переход. Пусть в графе вершин, тогда сумма их степеней равна Если в графе есть вершина степени выкинем её. Сумма степеней при этом уменьшится на и станет больше

Тогда новая средняя степень станет больше

В полученном графе по предположению индукции можно найти индуцированный подграф, в котором степень всех вершин не меньше что и требовалось.

Перейдём к решению задачи. В исходном графе количество рёбер одного из трёх цветов (скажем, красного) не меньше чем

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

В каждой паре

имеется не более одной вершины, смежной с (иначе сразу найдётся цикл длиной Значит, остальные не менее чем рёбер ведут из в вершины пути с номерами, большими чем Все эти номера нечётны (иначе сразу найдётся нечётный цикл большой длины). Следовательно, максимальный из этих номеров не меньше чем

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

Повторим проведённое рассуждение. В полном двуцветном графе на вершинах количество рёбер одного из двух цветов (зелёного) не меньше чем

Сумма зелёных степеней не меньше и средняя зелёная степень не меньше Поэтому в нем можно выбрать подграф, в котором у всех вершин зелёные степени не меньше

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

Мы получили зелёный цикл длиной не менее Можно считать, что его длина чётна. Отметим в нём вершины через одну (как минимум вершины). Если какие-то две из них соединены зелёным ребром, то образуется два нечётных цикла, сумма длин которых не меньше чем значит, один из них имеет длину не меньше Следовательно, отмеченные вершины попарно связаны рёбрами третьего цвета и среди них уже любые образуют цикл длиной