Rozklad na dva k-faktory
Úloha číslo: 3628
Má-li \(2k\)-regulární graf sudý počet hran v každé komponentě, potom má dva hranově disjunktní \(k\)-faktory. Dokažte.
(Definice: \(k\)-regulární graf má všechny vrcholy stupně \(k\); faktor je podgraf se stejnou množinou vrcholů; \(k\)-faktor je \(k\)-regulární faktor).
Řešení
Každou komponentu \(C\) rozložíme na dva \(k\)-faktory nezávisle na ostatních komponentách.
Komponenta \(C\) indukuje souvislý eulerovský graf, tedy má uzavřený eulerovský tah. Tento tah má podle předpokladů sudý počet hran. Postupujeme podle tahu a střídavě rozdělujeme hrany do dvou skupin – hrany na lichých pozicích v tahu do jedné skupiny, hrany v sudých do druhé.
Návštěvou libovolného vrcholu přibudou do obou skupin po jedné hraně; u prvního vrcholu je první hrana vyvážena přidáním poslední hrany do druhé skupiny.
Protože u každého vrcholu rozdělíme všechny přilehlé hrany do dvou stejně velkých skupin, má v rámci každé skupiny každý vrchol stupeň \(k\).