Eulerovský graf a sjednocení kružnic
Úloha číslo: 3626
Dokažte, že hrany každého eulerovského grafu lze rozložit na disjunktní sjednocení kružnic.
Je rozklad jednoznačný? Pokud ne, je počet kružnic v rozkladu dán jednoznačně?
Řešení
Indukcí: Eulerovský graf má uzavřený eulerovský tah. Pokud za \(C\) zvolíme nejkratší část tahu mezi dvěma výskyty stejného vrcholu, potom hrany \(C\) určují kružnici.
Graf \(G-C\) je eulerovský, tedy z indukčního předpokladu je disjunktním sjednocením kružnic. Přidáním \(C\) do tohoto sjednocení dostaneme všechny hrany \(G\).
Rozklad ani počet kružnic nejsou dány jednoznačně, např. \(K_5\) lze rozložit na dva pěticykly nebo na dva trojúhelníky a čtyřcyklus.