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\).

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze