Dimostrazione della teoria dei grafi

Question

Non sono in grado di fornire una prova riguardo a questa affermazione -

Considera G un grafo planare connesso. Se G non è bipartito, qualsiasi inclusione planare di G ha almeno 2 facce con grado dispari.

Qualcuno può aiutarmi con la prova?

Answer 1

Poiché G non è bipartito, G contiene un ciclo dispari C. Let $F_{1},F_{2},......,F_{k}$essere le facce all'interno di C nell'incorporamento planare. Considera la somma dei gradi di queste facce.

• Ogni arco in C viene contato una volta.
• Sia D l'insieme di archi su qualsiasi confine di qualsiasi $F_{i}$, ma non su C.

Ogni bordo in D viene contato due volte.

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

Da $|E(C)|$ è strano e $2|D|$ è anche,

$\sum_{i}$ $\deg(F_{i})$ è strano, quindi $\deg(F_{i})$ deve essere strano per alcuni $i$

Quindi almeno una faccia all'interno di C ha un grado dispari.

Lo stesso argomento può essere utilizzato per dimostrare che almeno una volta la faccia esterna a C ha un grado dispari.