Задача
COM-B2-M06-P010 Большая одноцветная звезда
#10
★★★☆☆ Уровень 3 из 5
В полном графе \(K_{2m}\) рёбра покрашены в красный и синий цвета. Докажите, что найдётся вершина, из которой выходит не менее \(m\) рёбер одного цвета.
Возьмите любую вершину.
Из любой вершины выходит \(2m-1\) рёбер. По усиленному принципу Дирихле среди этих рёбер есть хотя бы \(m\) рёбер одного цвета. Поэтому подходит даже произвольная вершина.
Простая, но часто используемая звёздная форма Рамсея.