Задача 30816

Темы:    [ Теория графов (прочее) ] [ Раскраски ] [ Принцип Дирихле (прочее) ]

Сложность: 4 Классы: 7,8

Условие

Каждое из рёбер полного графа с 17 вершинами покрашено в один из трёх цветов.
Докажите, что есть три вершины, все рёбра между которыми – одного цвета.

Решение

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

Источники и прецеденты использования

web-сайт
задача
книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	34
книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	13
Название	Графы-2
Тема	Теория графов
задача
Номер	038