COM-B2-M06-P018 Острая оценка \(R(3,4)\le9\)

Рассмотрите красный граф: в нём нет треугольников и нет независимого множества из \(4\) вершин. Оцените степени.

Переведём задачу в раскраску рёбер \(K_9\): красный цвет — знакомство, синий — незнакомство. Предположим, что нет красного треугольника и нет синего \(K_4\). Рассмотрим красный граф \(G\).

Граф \(G\) не содержит треугольников. Кроме того, в нём нет независимого множества из \(4\) вершин, потому что такое множество соответствовало бы синему \(K_4\).

Покажем, что степень любой вершины в \(G\) не больше \(3\). Действительно, если у вершины \(v\) есть \(4\) красных соседа, то между этими соседями не может быть красных рёбер, иначе возникнет красный треугольник с \(v\). Значит, эти \(4\) соседа образуют независимое множество в \(G\), то есть синий \(K_4\). Противоречие.

Если бы степень каждой вершины была ровно \(3\), сумма степеней равнялась бы \(9\cdot3=27\), что невозможно, потому что сумма степеней графа чётна. Значит, есть вершина \(v\) степени не больше \(2\).

Рассмотрим вершины, не смежные с \(v\) в красном графе. Их не меньше \(9-1-2=6\). В индуцированном на них красном графе также нет красного треугольника. По факту \(R(3,3)=6\), среди этих \(6\) вершин найдутся либо красный треугольник, либо независимая тройка. Красного треугольника нет, значит, есть независимая тройка.

Эта независимая тройка вместе с \(v\) образует независимое множество из \(4\) вершин в красном графе, то есть синий \(K_4\). Противоречие. Следовательно, нужная группа людей существует.

Сильная задача: вместо простой рекурсии используется графовая переформулировка через треугольники и независимые множества.