Как раскрасить граф, чтобы не было одноцветных треугольников?

В этой публикации я разберу два задачи из теории графов, где одновременно фигурируют лемма Турана и числа Рамсея.

Напомню, что лемма Турана в общем виде звучит так.
Наибольшее число ребер у графов, имеющих v вершин и у которого нет n попарно соединённых вершин равно
ex(v,n)=(n-2)(v^2-r^2)/(2n-2)+r(r-1)/2,
где r - остаток при делении v на (n-1).

Числом Рамсея r(m,n) называется минимальное количество человек в компании, в которой обязательно найдётся либо m попарно знакомых, либо n попарно незнакомых.

Задача 1. Ребра графа на 300 вершинах покрашены в красный и синий цвета так, что нет одноцветных треугольников. Какое наибольшее число ребер может быть в таком графе?

Задача 2. Рёбра полный графа на 30 вершинах покрасили в три цвета так, что рёбра первых двух цветов не образуют одноцветного треугольника. Какое наименьшее число рёбер третьего цвета может быть в таком графе?

Вспомним, что число Рамсея r(3,3)=6, т.е. в компании из шести человек обязательно найдётся либо трое попарно знакомых, либо трое попарно незнакомых; но при этом существует компания из пяти человек, в которой это свойство не выполняется.

Решение задачи 1. Заметим, если в графе есть полный подграф на 6 вершинах (K_6), то одноцветный треугольник найдется. По лемме Турана максимальное количество ребер в графе без K_6 равно [2*300^2/5]=36000, где квадратные скобки означают целую часть числа.

Пример строится так: разобьем 300 вершин на пять долей по 60 вершин и расположим их по кругу. Ребра, соединяющие вершины из соседних долей покрасим в красный цвет, остальные - в синий.

Решение задачи 2 аналогично. В полном графе на 20 вершинах 20*19/2=190 рёбер. В графе без K_6 рёбер не более [2*20^2/5]=160 рёбер, поэтому рёбер первого и второго цвета не более 160. Значит, рёбер третьего цвета не менее 30.

Пример строится таким же образом, как и пример для задачи 1.