Santa Claus — 2021-11-30 12:22 (401 days ago) — edit — reply
Stačí se na graf podívat jako na orientovaný graf a každou hranu nahradit dvěma hranami v obou směrech. Graf bude určitě slabě souvislý (i silně), a každý vrchol bude mít stejný počet vstupních a výstupních hran, protože pro každou incidentní hranu vrcholu přidáme vstupní a zároveň výstupní hranu. Takovýto graf má uzavřený eulerovský tah, tudíž ho lze nakreslit jedním tahem a původní graf lze nakreslit stejným způsobem.