dowód na $e\leq 3(v-2)$ [Dlaczego $d(f) \geq 3$?]

Question

Oto dobrze znane twierdzenie: „Dla wykresu planarnego $G$, gdyby $v\geq3$ następnie $e\leq 3(v-2)$"

Przejrzałem swoją dyskretną notatkę z matematyki i nagle pytanie przyszło mi do głowy.

Kiedy udowadniamy $e\leq 3(v-2)$ dla wykresu planarnego, $G$. Użyliśmy$d(f) \geq 3$.

W mojej notatce powiedział mi, dlaczego tak jest $d(f) \geq 3$ to „każda ściana jest ograniczona co najmniej trzema krawędziami, ale każda krawędź graniczy z dwiema ścianami”.

Kiedy pierwszy raz to zobaczyłem, było dla mnie jasne. Ale czas minął, wątpię w to.

Ponieważ ... Pozwólcie, że zasugeruję poniżej przykład przeciwny.

Powyższy wykres jest wykresem planarnym i $v=3, e=2,f=1$. Ale$d(f) \lt 3$ (Tj. Twarz nie jest ograniczona trzema krawędziami)

Nadal nie wiem, w jakim celu się pomyliłem.

Każda pomoc będzie mile widziana.

Answer 1

Twój kontrprzykład jest omawiany w tej odpowiedzi . Ponieważ krawędzie są granicami tej samej ściany, w dowodzie „granica twarzy” ma 4 krawędzie (każda krawędź jest liczona dwukrotnie).