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