Задача
Каждое из рёбер полного графа с 17 вершинами покрашено в один из трёх цветов. Докажите, что есть три вершины, все рёбра между которыми – одного цвета.
Решение
Из произвольной вершины выходит по крайней мере 6 рёбер одного цвета (пусть красного). Рассмотрим полный граф на 6 вершинах, в которые ведут эти рёбра. Если хотя бы одно из рёбер этого графа – красное, то есть красный "треугольник". В противном случае этот граф – двухцветный, и согласно задаче 130815 в нём есть одноцветный "треугольник".
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет