Задача
COM-B2-M06-P017 Один цвет связен
Рёбра полного графа \(K_n\) покрашены в красный и синий цвета. Докажите, что красный граф или синий граф связен.
Если красный граф не связен, посмотрите на рёбра между его компонентами.
Если красный граф связен, всё доказано. Пусть он не связен. Тогда его вершины разбиваются на несколько красных компонент.
Любое ребро между двумя разными красными компонентами не может быть красным, иначе эти компоненты соединились бы. Значит, все такие рёбра синие.
Покажем, что синий граф связен. Если две вершины лежат в разных красных компонентах, между ними есть синее ребро. Если они лежат в одной красной компоненте, возьмём вершину из другой красной компоненты; обе связи с ней синие, поэтому есть синий путь длины \(2\). Следовательно, синий граф связен.
Это не клика, но тоже вынужденная одноцветная структура.