Počet stěn

Ukažte, že počet stěn v rovinném nakreslení grafu s \(n\ge 3\) vrcholy je nejvýše

Varianta
\(2n-4\),
Řešení
Bez újmy na obecnosti můžeme uvážit souvislé grafy, protože přidáním hran mezi komponentami se nám počet vrcholů ani stěn nezmění (přidáním dalších hran se může dokonce počet stěn zvýšit).

Nyní dosadíme odhad \(|E_G|\le 3 |V_G|-6\) do Eulerova vzorce \(|V_G|-|E_G|+s=2\) a dostaneme \(s\le 2|V_G|-4\).
Varianta
\(n-2\), pokud graf neobsahuje žádné trojúhelníky.
Řešení
Dosazením \(|E_G|\le 2 |V_G|-4\) do \(|V_G|-|E_G|+s=2\) a dostaneme \(s\le |V_G|-2\).