4.4. Раскраска ребер графа

Рассмотрим полный граф с вершинами (который, очевидно, неплоский при и предположим, что некоторые его ребра окрашиваются в красный цвет, а оставшиеся ребра — в голубой. Найдем наименьшее число треугольников, все три стороны которых будут окрашены при этом одним цветом (монохроматические треугольники), Эта задача была впервые решена Гудманом [23], но мы приведем здесь более простое доказательство, предложенное Саувом [40],

Теорема 4.18. Пусть в полном графе с вершинами, число треугольников с тремя голубыми сторонами, соответствующее число треугольников с красными сторонами; тогда число монохроматических треугольников удовлетворяет неравенству

где неотрицательное целое число, Граница является точной, равенство выполняется для каждого и некоторого (красно-голубого) раскрашивания.

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

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

где — число сочетаний из вершин по две,

Аналогично,

Легко проверить, что найденный вес минимален при

Таким образом, общий вес всех вершин удовлетворяет неравенству

и

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

Для того чтобы доказать равенство при приведем рассуждения Лордена [32].

Пометим вершины и окрасим в красный цвет ребра, соединяющие пары вершин, сумма индексов

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

Покажите, что при существует красных треугольников. Доказательство этого равенства при нечетном дано в работе [40].

Теорема 4.19. В любом полном графе с вершинами

где число вершин, с каждой из которых вершина связана красными ребрами [32].

Доказательство. Вершине инцидентны красных ребер и голубых ребер. Следовательно, существует пар разноцветных ребер, причем каждая пара образует две стороны разноцветного треугольника. Так как третье ребро треугольника либо красное, либо голубое, то две оставшиеся вершины будут иметь красно-голубые пары. Следовательно, число разноцветных треугольников равно

Общее число треугольников равно сумме числа одноцветных треугольников и числа разноцветных треугольников. Таким образом, теорема доказана. Аналогичные задачи, могут возникнуть при раскраске графа в несколько цветов, однако в этом случае не существует столь же простых теорем.