Задача
COM-B2-M06-P019 Три цвета на \(17\) вершинах
Рёбра полного графа \(K_{17}\) покрашены в три цвета. Докажите, что существует одноцветный треугольник.
Из одной вершины выходит \(16\) рёбер. Найдите \(6\) рёбер одного цвета.
Выберем вершину \(v\). Из неё выходит \(16\) рёбер трёх цветов, поэтому по принципу Дирихле хотя бы \(6\) из них имеют один цвет. Пусть это красные рёбра к множеству \(A\) из \(6\) вершин.
Если внутри \(A\) есть красное ребро, то оно вместе с \(v\) образует красный треугольник. Если красных рёбер внутри \(A\) нет, то все рёбра внутри \(A\) покрашены двумя оставшимися цветами.
По факту \(R(3,3)=6\) в двухцветной раскраске рёбер на \(6\) вершинах есть одноцветный треугольник. Он будет одноцветным в одном из двух оставшихся цветов. Значит, в исходной трёхцветной раскраске одноцветный треугольник тоже существует.
Первый аккуратный пример многоцветного Рамсея.