k-regulární hranově (k-1)-souvislý graf
Úloha číslo: 3270
Dokažte, že každý \(k\)-regulární hranově \((k-1)\)-souvislý graf na sudém počtu vrcholů má perfektní párování.
Nápověda
Postupujte obdobně jako v důkazu věty, že každý kubický graf bez mostů má perfektní párování.
Řešení
Ověříme Tutteho podmínku. Nechť \(S \subset V(G)\). Počet lichých komponent v grafu \(G-S\) označme \(C_o(G,S)\). Díky souvislosti vede z každé liché komponenty alespoň \(k-1\) hran.
Pokud je \(k\) je liché, bude se v liché komponentě vytvářet lichý počet půlhran. Tedy z každé liché komponenty musí vést lichý počet hran. A protože \(k-1\) je sudé, musí vést ven alespoň \(k\) hran.
Pokud bude \(k\) sudé, bude se v každé komponentě vytvářet sudý počet půlhran a tudíž sudý počet hran povede ven. A protože \(k-1\) je liché, musí vést ven alespoň \(k\) hran.
Celkem \(k\cdot C_o(G,S)\) hran vede z lichých komponent. Protože je daný graf \(k\)-regulární, a \(S\) má pokýt všechny hrany vycházející z lichých komponent, musí pro velikost množiny \(S\) platit: \(k|S| \geq k\cdot C_o(G,S)\). Po zkrácení \(k\) dostáváme Tutteho podmínku.