Задача
COM-B2-M06-P006 Одноцветный треугольник в \(K_6\)
#6
★★★☆☆ Уровень 3 из 5
Докажите, что при любой красно-синей раскраске рёбер полного графа \(K_6\) найдётся одноцветный треугольник.
Выберите вершину и найдите три ребра одного цвета из неё.
Выберем вершину \(v\). Из неё выходит \(5\) рёбер, поэтому хотя бы \(3\) из них одного цвета. Пусть это красные рёбра к вершинам \(a,b,c\).
Если хотя бы одно из рёбер \(ab,bc,ca\) красное, то вместе с \(v\) оно образует красный треугольник. Если ни одно из этих рёбер не красное, то все они синие, и вершины \(a,b,c\) образуют синий треугольник.
Главная классическая задача модуля.