[Teoria grafów] Ilość krawędzi w grafie planarnym

[matinf]

Witam,

Weźmy graf planarny, taki że każdy jego region (ściana) jest otoczona dokładnie trzeba krawędziami.
Co więcej nie ma wierzchołków stopnia zero.
Pokazać, że \(\displaystyle{ |E| = 3|V| - 6}\).

Łatwo jest oszacować z góry tą ilość krawędzi poprzez:
\(\displaystyle{ |E| \le 3|V| - 6}\)
Tak samo musi się udać oszacować z dołu. Wtedy będzie wszystko w porządku, ale jakoś nie widzę jak.

[miodzio1988]

Łatwo jest oszacować z góry tą ilość krawędzi poprzez:
\(\displaystyle{ |E| \le 3|V| - 6}\)

W tym tonie zatem możemy napisać

Łatwo jest oszacować z dołu tą ilość krawędzi poprzez:
\(\displaystyle{ |E| \ge 3|V| - 6}\)

I koniec dowodu

[matinf]

Łatwo jest oszacować z góry tą ilość krawędzi poprzez:
\(\displaystyle{ |E| \le 3|V| - 6}\)

W tym tonie zatem możemy napisać

Łatwo jest oszacować z dołu tą ilość krawędzi poprzez:
\(\displaystyle{ |E| \ge 3|V| - 6}\)

I koniec dowodu

Zgadzam się ze wszystkim. Jak szacujesz ?-- 21 sie 2014, o 14:10 --Dopiero teraz zrozumiałem o co Tobie chodzi. Jako proste ćwiczenie wykonaj sobie szacowanie z góry,

[miodzio1988]

Jako proste ćwiczenie wykonaj sobie szacowanie z dołu zatem. Jak w jedną stronę można tak napisać to i w drugą bez problemu

[Kartezjusz]

Pokaż jak szacowałeś