Задача
Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий.
Докажите, что либо "красный", либо "синий" граф не является плоским.
Решение
Пусть оба эти графа – плоские. Тогда у них вместе не более, чем (3·11 – 6) + (3·11 – 6) = 54 ребра (см. задачу 130799). Однако в полном графе с 11 вершинами 55 ребер. Противоречие.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет