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.

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