Задача 024 — Задачи на Графы

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

Подсказка

Лемма: Ребра полного графа на $2^{n}$ вершинах можно раскрасить в $n$ цветов так, чтобы граф с ребрами любого цвета был двудольным.

Решение

Доказательство: Лемма легко доказывается индукцией по $n$ , база для $n=1$ очевидна. Переход тоже несложен: разобьем вершины на две группы по $2^{n-1}$ вершине, все ребра между группами покрасим в цвет $n$ , граф из ребер этого цвета будет очевидно двудольным. Теперь для каждой из половинок покрасим ребра в цвета $1,2, \ldots, n-1$ (это можно по индукционному предположению). Графы этих цветов также будут двудольными, так как состоят из двух несвязанных двудольных частей каждый.

Теперь перейдем к решению задачи. Легко покрасить вершины данного графа $G$ степени не более 1000 правильным образом в $1024=2^{10}$ цветов (и даже в 1001 цвет). Теперь, рассмотрим раскраску в 10 цветов ребер полного графа на 1024 вершинах (вершины которого занумерованы цветами вершин графа $G$ ), в которой граф каждого цвета двудолен. Покрасим все ребра графа $G$ между вершинами цветов $i$ и $j$ также, как и ребро между вершинами $i$ и $j$ в раскраске полного графа. Очевидно, нечетных циклов в графе ребер любого цвета не будет.