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

   Решение

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

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

Прислать комментарий

Условие

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

Решение

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

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