---
# System prepended metadata

title: Domácí úkol 9.3 - bdre

---

# Domácí úkol 9.3 - bdre
Jelikož vložení vrcholu do hrany nijak nezmění stěny grafu, můžu vrcholy stupně $2$ "přeskočit" (topologická kontrakce) až na smyčky - např. každou kružnici mohu redukovat na vrchol se smyčkou a stále mám $1$ vnitřní a $1$ vnější stěnu. 
Obarvení stěn 2 barvami pak dokazuje bipartitnost duálu.
V první implikaci se pokusím dokázat, že je-li graf eulerovský, pak jej můžu rozložit na kružnice, které jsou v sobě vnořené, nebo mají pouze společný vrchol (výše zmíněnými kontrakcemi pak dostanu "balónek" (jednotlivé vrstvy mají střídavé barvy) nebo "větrník" (každý list má stejnou barvu)).
Tyto útvary pak budou spojeny mezi sebou buďto po kružnici nebo sudým počtem násobných hran (rovinnost je zachována).

V druhém případě je počet stěn mezi těmito vrcholy vždy lichý, a tak můžeme stěny obarvovat z vnějšku.

Jsou-li centrální vrcholy spojeny po kružnici, zaměříme se na ind. podgraf ohraničený touto kružnicí.
Jelikož vrcholy kružnice mají sudý stupeň, uvnitř této kružnice musí také existovat eulerovský graf. Stěny vevnitř kružnice se pak nebudou dotýkat vnější stěny - vnitřní část kružnice pak můžeme považovat za vnější část zkoumaného (indukovaného) podgrafu.
