Олимпиадное задание по теории графов: неплоский полный граф K5
Докажите, что граф, имеющий пять вершин, каждая из которых соединена ребром со всеми остальными, не является плоским.
Разобрать решение
У этого графа 10 рёбер, поэтому не выполнено неравенство E ≤ 3V – 6. Согласно задаче 130798 он не может быть плоским.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.