Pokud nějaká stěna není trojúhelníková, lze ji rozdělit přidáním dodatečných hran na dvě nebo více stěn.
Podle Eulerovy formule má graf nyní \(3n-6\) hran, z nichž lze vytvořit \(\frac{2}3(3n-6)\) trojúhelníkových stěn, z nichž jedna je vnější.
Odpověď
Daný rovinný graf může mít nejvýše \(2n-5\) vnitřních stěn.
Varianta
Stejná úloha s dodatečnou podmínkou, že vnější stěna grafu je ohraničena cyklem délky \(k\).
Řešení
Graf s maximálním počtem vnitřních stěn doplníme na triangulaci tak, že do vnější stěny přidáme \(k-3\) hran, čímž vznikne \(k-3\) stěn navíc. Výsledný graf má celkem \(2n-4\) stěn, z nichž \(2n-k-8\) odpovídá původním vnitřním stěnám.
Odpověď
Daný rovinný graf může mít nejvýše \(2n-k-8\) vnitřních stěn.