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