Santa Claus — 2021-12-30 20:16 (370 days ago) — edit — reply
Předpokládejme, že G je souvislý, jinak tvrzení neplatí (nesouvislý graf může mít bipartitní duál, ale z definice není eulerovský.). 1. duál $G^*$ rovinného souvislého grafu $G$ je bipartitní $\implies$ $G$ je eulerovský. Graf je souvislý, stačí dokázat, že každý vrchol má sudý stupeň. Každý vrchol v grafu odpovídá stěně v duálu. Tato stěna má délku rovnou stupni vrcholu, protože každá vrcholu incidentní hrana tvoří hranu v hranici stěny duálu. Tato hranice v duálu ale musí mít sudou délku, protože v opačném případě by se jednalo o isomorfismus lichého cyklu, který sám není bipartitní, a tudíž by nebyl bipartitní ani původní duál. S výše zmíněné rovnosti ale vyplývá, že vrchol v grafu odpovídající stěně v duálu má sudý stupeň. Každý vrchol má tedy sudý stupeň, graf je eulerovský. 2. $G$ je eulerovský $\implies$ duál $G^*$ rovinného grafu $G$ je bipartitní. Definice: eulerovský multigraf je multigraf, který je souvislý a má každý vrchol sudého stupně. Dokažme tvrzení pro eulerovský multigraf. Jednoduchý graf je speciálním případem. Dokažme indukcí podle počtu vrcholů $G$. Základní případ: $G$ má jeden izolovaný vrchol se smyčkami. Je eulerovský, protože každá smyčka přispívá ke stupni dvojkou a jeho duál je bipartitní, protože stěny tvořené smyčkami obarvíme jednou barvou a vnější stěnu druhou. Indukční krok: Dostaneme graf, který je eulerovský. Odeberme z něj vrchol $v$ a hrany spojme takto: (Viz připojený obrázek) 1. Vezmeme dvě "sousedící hrany" incidentní vrcholu $v$, neboli dva sousedící vrcholy duálu, přiřadíme jim číslo 1 a pak po obvodu vrcholu přiřazujme rostoucí čísla vždy "protějším" hranám - prostě stoupající čísla ve směru od druhé zvolené hrany. 2. Takto očíslujeme všechny incidentní hrany do číselných párů - je jich totiž sudý počet, protože vrchol má sudý stupeň. 3. Spojme hrany se stejným číslem do jedné. (prosím viz obrázek pro objasnění) V takovémto zmenšeném multigrafu zůstavají všechny ostatní vrcholy sudého stupně. Mohli jsme ale narušit souvislost grafu. Vznikne nám tedy jedna až několik eulerovských komponent souvislosti. Na každou z nich aplikujme předpoklad, že jejich duály jsou bipartitní. Z toho ale plyne, že celý složený graf je bipartitní, stačí obarvit vnější stěny komponent (vrcholy duálu) stejnou barvou (v pojetí že bipartitnost je 2barvení). A původní graf vytvoříme opětovným přidáním vrcholu $v$ a rozpojením hran v opačném procesu, 2obarvení stěn bude zachováno, tedy duál je bipartitní.
Attachment (pdf)