Задача
COM-B2-M06-P003 Одноцветная дорожка длины два
#3
★★☆☆☆ Уровень 2 из 5
Докажите, что при любой красно-синей раскраске рёбер \(K_4\) найдётся путь из двух рёбер одного цвета.
Посмотрите на три ребра, выходящие из одной вершины.
Выберем вершину \(v\). Из неё выходят \(3\) ребра двух цветов. По принципу Дирихле два из них одного цвета, скажем \(va\) и \(vb\).
Тогда \(a-v-b\) — путь из двух рёбер одного цвета.
Показывает разницу между слабой и сильной вынужденной структурой.