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ášť.

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