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

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

Будем решать задачу индукцией по числу цветов

База Если ребра единственного цвета образуют треугольник, то его вершины можно распределить по одной по трем группам. Если они образуют пучок, то достаточно отнести вершину пучка в одну группу, а все остальные вершины – в другую.

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

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

Докажем, что не существует графа, состоящего из треугольников, степень каждой неизолированной вершины в котором Это завершит решение задачи по индукции. Отметим, что в любом таком графе есть хотя бы неизолированные вершины. Посчитаем двумя способами количество ребер в нем. С одной стороны, оно равно так как ребра можно разбить по цветам; цветов ровно а ребер фиксированного цвета – ровно 3. С другой, так как степень каждой неизолированной вершины то число ребер Значит, натуральное число должно удовлетворять неравенству

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