Příklad 1. V 2. příkladu na cviku jsme si dokázali, že Eulerovský graf lze rozložit na hranově disjunktní sjednocení kružnic. Ukažte, že:
(2 body za těžší verzi, 1 bod za lehčí)
Příklad 2. Pro grafy $G(V,E)$ a $H(V',E')$ označíme $G\times H$ graf $G'(V\times V',E'')$ takový, že $$E'' = \{\{(u,v),(u,v')\}\mid u\in V, v,v'\in V',\{v,v'\}\in E'\}\cup\{\{(u,v),(u',v)\}\mid u,u'\in V, v\in V',\{u,u'\}\in E\}.$$ Jinými slovy, pro každý vrchol grafu $G$ si vezmeme jednu kopii grafu $H$, a sobě odpovídající vrcholy v těchto kopiích pospojujeme tak, jak byly pospojované původní vrcholy v $G$. Ilustraci najdete například na příslušné stránce Wikipedie.
Mějme eulerovský graf $G$. Dokažte, že $G\times C_4$ je také eulerovský.(2 body)
Samozřejmě platí i silnější tvrzení, které říká, že pro každé dva eulerovské grafy $G, H$ je $G\times H$ eulerovský. Doufal jsem ale, že bude zadání takto představitelnější.