Provando a questão da teoria dos grafos

Aug 16 2020

Não consigo apresentar uma prova em relação a esta declaração -

Considere G como um grafo planar conectado. Se G não for bipartido, então qualquer incorporação planar de G tem pelo menos 2 faces com grau ímpar.

Alguém pode me ajudar com a prova?

Respostas

4 PrabhSimranSinghBadwal Aug 16 2020 at 18:43

Uma vez que G não é bipartido, G contém um ciclo ímpar C. $F_{1},F_{2},......,F_{k}$ser as faces dentro de C na incorporação planar. Considere a soma dos graus dessas faces.

  • Cada aresta em C está sendo contada uma vez.
  • Seja D o conjunto de arestas em qualquer fronteira de qualquer $F_{i}$, mas não em C.

Cada aresta em D é contada duas vezes.

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

Desde a $|E(C)|$ é estranho e $2|D|$ é mesmo,

$\sum_{i}$ $\deg(F_{i})$ é estranho então $\deg(F_{i})$ deve ser estranho para alguns $i$

Portanto, pelo menos uma face dentro de C tem grau ímpar.

O mesmo argumento pode ser usado para mostrar que pelo menos uma vez a face fora de C tem grau ímpar.