The Postal Owl

## 10. cvičení

### $K_5$ a $K_{3,3}$

První nerovinnost se dokáže přes základní odhad na počet hran $|E| \leq 3|V| - 6$, u druhého si všimneme, že neobsahuje žádný trojúhelník a tedy můžeme použít těsnější odhad $|E| \leq 2|V| - 4$.

### Nejednoznačnost duálu

Hlavní myšlenka je, že lze změnit sousednosti stěn změnou nakreslení téhož grafu. Např. lze nakreslit trojúhelník a na dva vrcholy pověsit trojúhelníky. Pokud trojúhelníky nakreslíme oba dovnitř nebo jeden dovnitř a jeden ven, dostaneme různé duály.

### [Rovinný eulerovský](https://matematika.reseneulohy.cz/4113/kresleni-jednim-tahem)

Na cvičení jsem říkal, že tento důkaz se musí udělat pečlivě. Představuji si to takhle. Vrchol $v$ má nějakých $2k$ sousedů, kteří jsou spárování následujícím způsobem: pokud tah $T_1$ (vizte obrázek v úlohách) opouští $v$ do vrcholu $u$ a pak se vrací do $v$ z vrcholu $w$, tak $u$ a $w$ jsou spárování. Jeden daný tah nám i říká, v jakém směru jsou vrcholy spárovány, např. že vede šipka z $u$ do $w$ (odpovídající $T_1$). Pokud $T_1$ obrátíme, tak je to jako obrácení šipky, aby vedla z $w$ do $u$.

Tedy okolí vrcholu $v$ si můžeme představit jako $v$ uprostřed a kolem něj jeho sousedé v tom pořadí, v jakém jsou v nějakém rovinném nakreslení $G$. Mezi těmito sousedy teď jsou šipky. Řekněme, že toto jsou červené šipky. Dáme ale máme dány modré šipky, které odpovídají tomu, že v tahu $T$ po $T_0$ odpovídá $T_1$, potom $T_2$ atd., tedy když se v $T_1$ vrátíme např. do $w$, tak máme začít v počátečním vrcholu $T_2$ a z něj se vrátíme koncovým vrcholem $T_2$ atd. Takže pokud $z$ je počátečním vrcholem $T_2$ a $w$ je koncovým vrcholem $T_1$, tak budeme mít modrou šipku z $w$ do $z$.

Situaci si můžeme představit následovně. Nakreslíme si sousedství $v$ v takovém pořadí, v jakém se objevuje v našem nakreslení, tzn. doprostřed si nakreslíme $v$ a kolem něj jeho sousedy, tak jak jdou v nakreslení. Mezi sousedy nakreslíme červené a modré šipky, jak bylo popsáno výše. Tyto šipky dohromady tvoří kružnici, v této kružnici se protínají některé modré šipky a to nám vadí a chceme se toho zbavit.

Jaké umíme operace? 
Umíme operaci "prohození modrých šipek" -- když si vezmeme dvě modré šipky, třeba $xy$ a $wz$, tak je můžeme nahradit jinými dvěma šipkami $xz$ a $wy$ a náš obrázek stále odpovídá nějakému uzavřenému eulerovskému tahu -- vlastně jsme řekli, že když se vrátíme z tahu, který končí $x$, tak nemáme pokračovat do $y$, ale do $z$ a když se vrátíme přes $w$, tak nemáme pokračovat do $z$, ale do $y$.
Taky umíme operaci "otočení červené šipky", což je vlastně otočení odpovídajícího tahu (např. otočení $T_1$ je otočení šipky mezi $u$ a $w$), ale tato operace musí být doprovázena odpovídajícím prohozením modrých šipek, protože se najednou ze vstupního vrcholu stane výstupní a naopak.

Teď by se nám možná chtělo argumentovat, že kdykoliv uvidíme křížení modrých hran $xy$, $wz$, tak je prostě prohodíme, ale jak zaručíme, že jsme nějaké další křížení nevytvořili? Toho lze dosáhnout např. tím, že si vybereme $x,y,w,z$ tak, aby mezi $x,w$ a $y,z$ byla co nejmenší vzdálenost, tzn. nelze vybrat čtveřici, která by měla tyto dvojice vrcholů blíž. Pak už se dá uargumentovat, že takovýmihle prohozeními jsme schopni eliminovat všechna křížení.



### [Petersen](https://matematika.reseneulohy.cz/4109/nerovinnost-petersenova-grafu)

### Doplněk rovinného

Opět přes odhad na počet hran.

### [Nejvíc stěn](https://matematika.reseneulohy.cz/4111/maximalni-pocet-sten)

### [Platónská tělesa](https://matematika.reseneulohy.cz/4117/platonska-telesa)