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