Олимпиадная задача по теории графов и алгебре: неравенство 2E ≥ 3F
Докажите, что для плоского графа справедливо неравенство 2E ≥ 3F.
Разобрать решение
Поставим у каждого ребра две точки: по одной в каждом из прилегающих к нему кусков. В каждый кусок попадёт не меньше трёх точек, поэтому всего точек не меньше 3F. С другой стороны, точек ровно 2E.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.