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