Prouver la question de la théorie des graphes

Aug 16 2020

Je ne suis pas en mesure de fournir une preuve concernant cette déclaration -

Considérez G comme un graphe planaire connexe. Si G n'est pas bipartite, alors tout encastrement plan de G a au moins 2 faces de degré impair.

Quelqu'un peut-il m'aider avec la preuve?

Réponses

4 PrabhSimranSinghBadwal Aug 16 2020 at 18:43

Puisque G n'est pas bipartite, G contient un cycle impair C. Soit $F_{1},F_{2},......,F_{k}$être les faces à l'intérieur de C dans l'encastrement plan. Considérez la somme des degrés de ces faces.

  • Chaque arête en C est comptée une fois.
  • Soit D l'ensemble des arêtes sur n'importe quelle frontière de tout $F_{i}$, mais pas sur C.

Chaque arête en D est comptée deux fois.

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

Depuis $|E(C)|$ est étrange et $2|D|$ est même,

$\sum_{i}$ $\deg(F_{i})$ est étrange, donc $\deg(F_{i})$ ça doit être bizarre pour certains $i$

Donc au moins une face à l'intérieur de C a un degré impair.

Le même argument peut être utilisé pour montrer qu'au moins une fois la face à l'extérieur de C a un degré impair.