Vynechání dvou hran v kubickém grafu

Úloha číslo: 3267

Dokažte, že pro každé dvě hrany kubickeho grafu bez mostů existuje perfektní párování, které je neobsahuje.

  • Nápověda

    Postupujte obdobně jako pro jednu hranu.

  • Řešení

    Pokud jsou hrany sousední, využijeme fakt, že existuje párování, které obsahuje třetí hranu vedoucí do společného vrcholu předepsaných hran.

    Graf označme \(G\) a hrany \(e,f\). Graf \(G\) po odebrání hran \(e,f\) označme \(G’\).

    Pro spor nechť \(G’\) nemá perfektní párování. Tedy porušuje Tutteho podmínku a existuje \(S\subset V(G)\), že \(|S| < C_o(G’,S)\), kde pomocí \(C_o(G,S)\) označíme počet lichých komponent grafu \(G-S\).

    Všimneme si, že parita \(|S|\) a \(C_o(G’,S)\) je stejná, protože \(G\) má sudý počet vrcholů. Proto lze nerovnost zesílit na \(|S| \le C_o(G’,S)-2\).

    Pro počet hran \(\#e\) vedoucích do \(S\) v grafu \(G\) tedy platí: \( \#e \le 3|S| \le 3 C_o(G’,S)-6. \)

    Pokud jedna z hran spojuje vrcholy uvniř jedné komponenty nebo uvnitř \(S\), potom spor odvodíme podobně jako v úloze s jednou předepsanou hranou. Proto předpokládejme, že obě hrany spojují liché komponenty. Rozlišíme tři případy:

    • Hrany \(e,f\) spojují dvě liché komponenty do jedné sudé. Z této sudé vedou alespoň dvě hrany do \(S\). Potom \(C_o(G,S)=C_o(G’,S)-2\) a \(\#e \ge 3 C_o(G,S) +2 \), dohromady: \[ 3 C_o(G,S) +2 \le \#e \le 3|S| \le 3 C_o(G’,S)-6 = 3 C_o(G,S). \]
    • Hrany \(e,f\) spojují tři liché komponenty do jedné liché. Z této liché komponenty vede alespoň 5 hran do \(S\). Potom \(C_o(G,S)=C_o(G’,S)-2\) a \(\#e \ge 3 C_o(G,S) +2 \), což vede na stenou nerovnost jako v předchozím případě.
    • Hrany \(e,f\) spojují čtyři liché komponenty do dvou sudých. Z těchto sudých komponent vede alespoň 8 hran do \(S\). Potom \(C_o(G,S)=C_o(G’,S)-4\) a \(\#e \ge 3 C_o(G,S) +8 \), dohromady: \[ 3 C_o(G,S) +8 \le \#e \le 3|S| \le 3 C_o(G’,S)-6 = 3 C_o(G,S) +6. \]
Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze