k-regulární hranově k-souvislý graf
Úloha číslo: 3269
Dokažte, že každý \(k\)-regulární hranově \(k\)-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 souvuslosti vede z každé liché komponenty alespoň \(k\) hran. Celkem \(k\cdot C_o(G,S)\) hran vede z lichých komponent.
Protože je 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.
Poznamenejme ještě, že pro lichá \(k\) bude mít graf sudý počet vrcholů podle principu sudosti, ale pro sudá je třeba tento podmínku zaručit zvlášť.