Индукция в графах и теорема Турана

(a) Рассмотрим граф с вершинами в городах, ребра которого соответствуют дорогам. Докажем, что вершины этого графа можно покрасить в цвета правильным образом (то есть так, чтобы никакие две вершины одинакового цвета не были соединены ребром). Это равносильно утверждению задачи.

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

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

Теперь рассмотрим исходный граф На каждой его вершине напишем пару из двух чисел соответствующих ее цвету в графах и По построению, число может быть либо 1, либо 2, а число  – произвольным от до Ясно, что для любых двух вершин, соединенных ребром в графе эти пары различаются хотя бы по одной из координат. Изготовим окраску графа в новые цвета следующим образом: если на вершине написана пара и то окрасим ее в цвет, имеющий номер если то в цвет с номером Нетрудно проверить, что две вершины будут окрашены в один цвет тогда и только тогда, когда написанные на них пары совпали, и значит по замечанию выше построенная окраска является правильной. Также ясно, что число использованных в ней цветов не превосходит что и требовалось.

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

База для графа из одной вершины очевидна.

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

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

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

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