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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze