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. \]