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.

Preview