Доказательство вопроса теории графов

Aug 16 2020

Я не могу представить доказательства этого утверждения -

Рассмотрим G - связный плоский граф. Если G не двудольна, то любое плоское вложение G имеет не менее 2 граней нечетной степени.

Может ли кто-нибудь помочь мне с доказательством?

Ответы

4 PrabhSimranSinghBadwal Aug 16 2020 at 18:43

Поскольку G не двудольна, G содержит нечетный цикл C. Пусть $F_{1},F_{2},......,F_{k}$- грани внутри C в плоском вложении. Рассмотрим сумму степеней этих граней.

  • Каждое ребро в C считается один раз.
  • Пусть D - множество ребер на любой границе любого $F_{i}$, но не на C.

Каждое ребро в D считается дважды.

Так $\sum_{i}$ $\deg(F_{i})$ знак равно $|E(C)| + 2|D|$

поскольку $|E(C)|$ это странно и $2|D|$ даже,

$\sum_{i}$ $\deg(F_{i})$ странно, поэтому $\deg(F_{i})$ должно быть странно для некоторых $i$

Итак, по крайней мере одна грань внутри C имеет нечетную степень.

Тот же аргумент можно использовать, чтобы показать, что хотя бы одна грань вне C имеет нечетную степень.