Vnějškově rovinné grafy

Úloha číslo: 3279

Dokažte, že graf je vnějškově rovinný právě tehdy, když neobsahuje podrozdělení \(K_4\) a \(K_{2{,}3}\) jako podgraf.

Graf je vnějškově rovinný, pokud má rovinné nakreslení takové, že všechny vrcholy jsou incidentní s vnější stěnou.

  • Nápověda

    Přidej apexový vrchol (vrchol spojený se všemi ostatními) a převeď na rovinnost.

  • Řešení

    Mějme graf \(G\), který neobsahuje \(K_4\) a \(K_{2{,}3}\). Vytvoříme z něj graf \(G'\) přidáním jednoho nového vrcholu \(v\) spojeného hranou se všemi ostatními. Graf \(G'\) neobsahuje podrozdělení \(K_5\) ani \(K_{3{,}3}\). Tudíž je rovinný a můžeme ho nakreslit tak, aby \(v\) byl incidentní s vnější stěnou. Pak stačí \(v\) odebrat a získáme nakreslení vnějškové rovinné nakreslení \(G\), protože každý vrchol bude incidentní s vnější stěnou.

    Ještě ukážeme druhou implikaci. Mějme vnějškově rovinný graf \(G\). Chceme ukázat, že neobsahuje podrozdělení \(K_4\) ani \(K_{2{,}3}\). Sporem nechť obsahuje. Vezměme vnějškové rovinné nakreslení \(G\) a do vnější stěny přidejme vrchol \(v\) spojený se všemi vrcholy grafu \(G\). Výsledný graf bude rovinný. Navíc ale bude obsahovat podrozdělení \(K_5\) nebo \(K_{3{,}3}\) a to je spor s Kuratowského větou, že rovinné grafy neobsahují podrozdělení \(K_5\) ani \(K_{3{,}3}\).

  • Varianta

    Dokažte uvedenou charakterizaci vnějškově rovinných grafů bez užití Kuratowského věty.

  • Řešení

    Dopředná implikace: \(K_4\) ani \(K_{2{,}3}\) nelze nakreslit jako vnějškově roviné, prootže vnější cyklus vždy odděluje zbylý vrchol.

    Nahrazení cest hranami zachová vnějškovou rovinnost. Kdyby bylo vnějškově rovinné dělení \(K_4\), byl by vnějškově rovinný i samotný \(K_4\). Podobně pro \(K_{2{,}3}\). Proto vnějškově rovinný graf nemůže mít dělení \(K_4\) ani \(K_{2{,}3}\).

    Zpětnou implikaci dokážeme indukcí podle počtu hran. Spojení vnějškově rovinných nakreslení mostem nebo artikulací zachová vnějškovou souvislost. Bez újmy na obecnosti se můžeme omezit na dvousouvislé grafy. Ty lze vytvořit z cyklů přidáváním uší.

    Základ indukce, cykly, jsou vnějškově rovinné.

    Nalezneme v \(G\) ucho. Podle indukčního předpokladu má \(G\) po odebrání ucha vnějškově rovinné nakreslení. Protože je tento graf dvousouvislý, tak je vnější stěna omezena cyklem. Mohou nastat následující případy:

    • Ucho má délku alespoň dvě a spojuje sousední vrcholy cyklu, potom ho nakreslíme k vnější straně této hrany.
    • Ucho má délku alespoň dvě a spojuje nesousední vrcholy cyklu, potom \(G\) má dělení \(K_{2{,}3}\) a tudíž tento případ nemůže nastat.
    • Ucho je hrana a spojuje nesousední vrcholy cyklu ze stejné vnitřní stěny, potom ho nakreslíme do této stěny.
    • Ucho je hrana a spojuje nesousední vrcholy cyklu v různých vnitřních stěnách, potom \(G\) má dělení \(K_4\) a tudíž tento případ nemůže nastat.
Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze