2-faktorizace 2k-regulárního grafu
Úloha číslo: 3268
Dokažte Petersenovu větu o tom, že každý \(2k\)-regulární graf lze rozložit na \(k\) hranově disjunktních 2-faktorů. Dodejme, že \(k\)-faktor je graf, ve kterém mají všechny vrcholy stupeň \(k\).
Nápověda
S pomocí Eulerovského tahu převeďte hledání 2-faktoru ve \(2k\)-regulárním grafu na hledání perfektního párování v \(k\)-regulárním bipartitním grafu.
Řešení
Bez újmy na obecnosti předpokládejme, že je daný graf \(G\) souvislý, neboť jinak rozložíme každou komponentu zvlášť.
Protože je daný graf \(2k\)-regulární, má všechny stupně sudé, a tudíž jej lze nakreslit jedním uzavřeným tahem. Hrany grafu zorientujeme podle tahu. U každého vrcholu bude vstupní i výstupní stupeň přesně \(k\).
Každý vrchol rozdělíme na dva, kdy u jednoho ponecháme pouze vstupní hrany a u druhého pouze výstupní hrany. Výsledkem bude \(k\)-regulární bipartitní graf \(B\). Důstedkem Hallovy věty je, že hrany každého bipartitního \(k\)-regulárního grafu lze rozložit na \(k\) perfektních párování.
Hrany každého párování v \(B\) tvoří v grafu \(G\) hledaný 2-faktor, protože každý vrchol z \(G\) odpovídá dvěma vrcholům v \(B\). Tyto vrcholy navíc nejsou v \(B\) spojené hranou (ta by odpovídala smyčce v \(G\)) a oba jsou incidentní s jednou párovací hranu – pro každý vrchol z dvojice různou.