Монохроматические треугольники. 
Геометрическая теория графов

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

Если среди сторон этого треугольника есть как стороны одного, так и стороны другого цветов, то значит есть сторона (на рисунке это сторона В₂В₃) того же цвета, что и отрезки.

АВ/, AB₂ и А В ,. Ясно, что и в этом случае существует монохроматический треугольник (на рисунке это АВ₂В₃).

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

Каждой паре смежных ребер а и b присвоим вес со (а, Ь) по следующему закону:

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

Весом ш (А) вершины А будем называть сумму весов всех пар инцидентных ей ребер. Так как каждая пара смежных ребер входит ровно в один треугольник, то сумма весов всех вершин A_t(i =1, 2, …, 6) графа будет равна сумме весов всех треугольников и будет в шесть раз больше, чем количество монохроматических треугольников. Если обозначить через К и С количество красных и синих треугольников в исходном графе, то количество монохроматических треугольников будет определяться выражением:

Оценим вес одной вершины А. Предположим, что к этой вершине примыкает к красных ребер, тогда к вершине А примыкает также 5 -к синих ребер. Имеем:

Здесь первое слагаемое соответствует сумме весов красных ребер, второе — сумме весов синих ребер, а третье — сумме весов разноцветных ребер, инцидентных вершине А. Упрощая это равенство, можем записать:

или.

Так как (о (А) — целое число, то со (А)> 2. Итак, для любой вершины Л, можем записать неравенство а>(А,)> 2. Складывая эти шесть неравенств и умножая результат 1.

на —, получим, что количество монохроматических.

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

Используя этот метод доказательства, можно оценить также минимальное количество монохроматических треугольников полного графа с произвольным количеством вершин. Именно, если ребра полного графа с п вершинами покрашены в синий и красный цвета, то количество монохроматических треугольников К+С удовлетворяет неравенству [2]: