Vyvážená orientace
Úloha číslo: 4314
Mějme neorientovaný graf, jehož všechny vrcholy mají sudé stupně. Dokažte, že je možné hrany zorientovat tak, aby se v každém vrcholu vstupní stupeň rovnal výstupnímu.
Řešení
Bez újmy na obecnosti je graf souvislý (jinak zpracujeme každou komponentu zvlášť).
Podle věty o charakterizaci eulerovskych tahů v souvislém grafu se sudými stupni existuje uzavřený eulerovský tah. Stačí projít tah v jednom z možných směrů a zorientovat hrany tak, jak jimi tah prochází.
