Задание олимпиады: одноцветные четверки вершин в полном графе 18
Каждое из рёбер полного графа с 18 вершинами покрашено в один из двух цветов.
Докажите, что есть четыре вершины, все рёбра между которыми – одного цвета.
Разобрать решение
Из произвольной вершины выходит по крайней мере 9 рёбер одного цвета (пусть красного). Рассмотрим полный граф на 9 вершинах, в которые ведут эти рёбра, и применим к нему результат задачи 130817.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.