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

Построим граф вершины которого — города, а ребра — авиамаршруты между городами. Будем красить ребра в красный и синий цвета в зависимости от того, какой авиакомпании принадлежит соответствующий маршрут. Требуется доказать, что в построенном графе существуют два непересекающихся нечетных цикла одного цвета.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

___________________________________________________________________________________________________________________________________________________________________

Лемма 2. Если каждое ребро полного графа (граф с -ю вершинами, каждая пара из которых соединена ребром) покрасить в один из двух цветов, и в этом графе нет одноцветного треугольника (цикла длины все ребра которого окрашены в один цвет), то в этом графе есть два непересекающихся (не имеющих общих ребер) цикла, каждый из которых окрашен в один цвет и имеет длину

Доказательство. Пусть — вершины графа. Рассмотрим ребра — если три из них имеют один и тот же цвет, то найдется одноцветный треугольник, что противоречит условию: действительно, пусть — красные, тогда все ребра должны быть синими (иначе получим красный треугольник), но тогда мы имеем синий треугольник. Итак, из каждой вершины выходят по два красных и два синих ребра.

Рассмотрим граф, состоящий из вершин и только красных ребер — в таком графе степень каждой вершины равна а значит, он либо является циклом длины либо разбивается на меньшие циклы. Если разбить граф на вершинах степени на меньшие циклы, то либо получим цикл из вершины (в наших условиях это невозможно), либо одноцветный треугольник, что также исключено (см. выше). Итак, граф на красных ребрах — цикл длины аналогичный вывод делаем для графа на синих ребрах. Лемма 2 доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к задаче: пусть — вершины графа и пусть — одноцветный треугольник в нем (его существование следует из леммы В графе также есть одноцветный треугольник, т.к. количество его вершин не меньше (даже — пусть это треугольник Если эти треугольники окрашены в один цвет, то решение завершено. Если же нет (допустим, — синий, а — красный), то рассмотрим ребра для — всего ребер и, согласно принципу Дирихле, среди них найдутся ребер одного цвета (без ограничения общности будем считать, что синего). Тогда для некоторого найдутся два синих ребра из тройки т.е. меем один синий и один красный треугольники с общей вершиной

Итак, “угол” — синий, а “угол” — красный. Рассмотрим граф Если в нем есть одноцветный треугольник, то решение завершено: берем его и соответствующий ему по цвету или Если в нет одноцветного треугольника, то, согласно лемме в ней найдутся два разноцветных цикла длины — в этом случае берем нужный из этих циклов в качетсве второго циклического маршрута. Доказательство утверждения задачи завершено.