Pytanie dotyczące teorii wykresów dowodzenia
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
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ń.