Pytanie dotyczące teorii wykresów dowodzenia

Aug 16 2020

Nie jestem w stanie przedstawić dowodu dotyczącego tego stwierdzenia -

Rozważmy G jako połączony graf planarny. Jeśli G nie jest dwudzielne, to każde płaskie osadzenie G ma co najmniej 2 ściany o nieparzystym stopniu.

Czy ktoś może mi pomóc z dowodem?

Odpowiedzi

4 PrabhSimranSinghBadwal Aug 16 2020 at 18:43

Ponieważ G nie jest dwudzielne, G zawiera nieparzysty cykl C. Niech $F_{1},F_{2},......,F_{k}$być ścianami wewnątrz C w płaskim osadzeniu. Rozważ sumę stopni tych twarzy.

  • Każda krawędź w C jest liczona raz.
  • Niech D będzie zbiorem krawędzi na dowolnej granicy dowolnego $F_{i}$, ale nie na C.

Każda krawędź w D jest liczona dwukrotnie.

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

Od $|E(C)|$ jest dziwne i $2|D|$ jest równa,

$\sum_{i}$ $\deg(F_{i})$ jest dziwne, więc $\deg(F_{i})$ dla niektórych musi być dziwne $i$

Więc przynajmniej jedna twarz wewnątrz C ma dziwny stopień.

Tego samego argumentu można użyć, aby wykazać, że przynajmniej raz twarz na zewnątrz C ma nieparzysty stopień.