k-regulární bipartitní graf
Úloha číslo: 3769
Dokažte, že hrany \(k\)-regulárního bipartitního grafu lze vyjádřit jako sjednocení \(k\) perfektních párování.
Nápověda
Dokazujte indukcí a použijte Hallovu větu.
Řešení
Jsou-li \(A, B\) části bipartitního grafu, potom pro každou \(I\subseteq A\) platí, že z \(I\) vychází právě \(k|I|\) hran. Pokud by \(Y=N(I)\) obsahovalo méně než \(|I|\) vrcholů, vedlo by do \(Y\) méně než \(k|I|\) hran, což nelze.
Hallova podmínka je splněna a proto v grafu existuje perfektní párování \(P\), tedy takové, které obsahuje všechny vrcholy grafu. Odebráním hran tohoto párování dostaneme \((k-1)\)-regulární bipartitní graf.
Jsou-li dle indukce hrany tohoto zmenšeného grafu rozložitelné na perfektní párování, přidáním \(P\) do rozkladu získáme rozklad původního grafu.