Задача
COM-B2-M06-P009 Если треугольников нет
#9
★★★☆☆ Уровень 3 из 5
Рёбра \(K_n\) покрашены в красный и синий цвета, и одноцветных треугольников нет. Докажите, что \(n\le5\).
Докажите, что из каждой вершины выходит не более двух красных и не более двух синих рёбер.
Возьмём вершину \(v\). Если из неё выходят три красных ребра к \(a,b,c\), то среди \(a,b,c\) не может быть красного ребра, иначе возникнет красный треугольник с \(v\). Значит, все рёбра между \(a,b,c\) синие, и получается синий треугольник. Противоречие.
Следовательно, красная степень любой вершины не больше \(2\). Аналогично синяя степень не больше \(2\). Но всего из вершины выходит \(n-1\) рёбер, значит, \(n-1\le4\), откуда \(n\le5\).
Альтернативное доказательство верхней оценки \(R(3,3)\le6\).