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