The Postal Owl

Dokážu dvě implikace:

Graf je maximálně rovinný $\implies$ graf je triangulace:

Sporem. Uvažme, že maximálně rovinný graf není triangulace, potom existuje stěna jeho nakreslení, která má délku čtyři nebo delší. Lze nakreslit jednoduchou křivku mezi vrcholy v této stěně, mezi kterými jednoduchá křivka není, tato křivka odpovídá hraně, kterou lze přidat do grafu, tudíž graf není maximálně rovinný, což je spor.

Graf je triangulace $\implies$ graf je maximálně rovinný:

Opět Sporem: Uvažme, že existuje jednoduchá křivka, kterou můžeme v nějakém nakreslení nakreslit z vrcholu do vrcholu  (mezi kterými ještě křivka není) tak, že nevytvoříme křížení. K tomu bychom potřebovali dva vrcholy, které jsou v jedné komponentě obloukové souvislosti a zároveň nejsou propojeny. Protože jsou ale v každé komponentě obloukové souvislosti (stěně) tři vrcholy a všechny tři už jsou propojeny, žádnou takovou dvojci nemáme. To je spor. Žádnou novou křivku tedy nakreslit nemůžeme a tedy ani přidat žádnou hranu.

U bodu 1. nezávisí na tom, jestli je hranice nakreslení stěny kružnice nebo ne,

Určitě má délku alespoň čtyři, a určitě obsahuje sled $a,e_{ab},b,e_{bc},c, e_{cd}, d$, kde platí $a \neq b$, $b \neq c$, $c \neq d$, protože smyčky jsou nepřípustné.

Dálé platí, že $a \neq c$, nebo $b \neq d$, jinak by se jednalo o nesmyslou hranici.

Potom můžeme propojit a a c nebo b a d a rozdělit tak stěnu na dvě.