Prueba de la pregunta de teoría de gráficos

Aug 16 2020

No puedo presentar una prueba con respecto a esta declaración:

Considere que G es un gráfico plano conectado. Si G no es bipartito, entonces cualquier incrustación plana de G tiene al menos 2 caras con grado impar.

¿Alguien puede ayudarme con la prueba?

Respuestas

4 PrabhSimranSinghBadwal Aug 16 2020 at 18:43

Dado que G no es bipartito, G contiene un ciclo impar C. Sea $F_{1},F_{2},......,F_{k}$sean las caras dentro de C en la incrustación plana. Considere la suma de los grados de estas caras.

  • Cada borde en C se cuenta una vez.
  • Sea D el conjunto de aristas en cualquier límite de cualquier $F_{i}$, pero no en C.

Cada borde en D se cuenta dos veces.

Entonces $\sum_{i}$ $\deg(F_{i})$ = $|E(C)| + 2|D|$

Ya que $|E(C)|$ es extraño y $2|D|$ incluso,

$\sum_{i}$ $\deg(F_{i})$ es extraño, entonces $\deg(F_{i})$ debe ser extraño para algunos $i$

Entonces, al menos una cara dentro de C tiene un grado impar.

Se puede usar el mismo argumento para demostrar que al menos una vez la cara fuera de C tiene un grado impar.