Předepsaná hrana v kubickém grafu
Úloha číslo: 3266
Nechť \(G\) je kubický graf bez mostů. Dokažte, že pro každou jeho hranu existuje perfektní párování, které ji obsahuje.
Nápověda
Postupujte obdobně jako v úloze, kdy párovaní určenou hranu neobsahuje. Odeberte oba vrcholy, které tvoří konce hrany. Využijte toho, že graf musí mít sudý počet vrcholů.
Řešení
Nechť \(G\) je kubický graf bez mostů. Kubické grafy splňují Tutteho podmínku, tedy pro každou \(S \subseteq V(G)\)platí, že \(|S| \ge C_o(G,S)\), kde \(C_o(G,S)\) označuje počet lichých komponent grafu \(G-S\).
Graf označme \(G\) a předepsanou hranu \(uv\). Graf \(G\) po odebrání vrcholů \(u,v\) označme \(G’\).
Pro spor předpokládejme, že \(G’\) nemá perfektní párování a tudíž pro něj neplatí Tutteho podmínka a existuje \(S’ \subseteq V(G’)\), že \(|S’| < C_o(G’,S’)\).
Kubické grafy jako je \(G\) mají podle principu sudosti sudý počet vrcholů a totéž platí i pro \(G’\). V důsledku má velikost \(S’\) a počet lichých komponent stejnou partitu. Proto lze nerovnost \(|S’| < C_o(G’,S’)\) zesílit na \(|S’| \le C_o(G’,S’)-2\).
Abychom získali řez \(S\) v grafu \(G\), položíme \(S=S’\cup \{u,v\}\). Doplněk \(S\) v \(G\) je stejný jako doplněk \(S’\) v \(G’\), proto \( C_o(G,S) = C_o(G’,S’)\).
Do lichých komponent grafu \(G\) má podle principu sudosti vést lichý počet hran. Protože graf \(G\) nemá mosty, vycházejí z každé liché komponenty alespoň tři hrany.
Protože \(G\) je kubický, vede do \(S’\) nejvýše \(3|S’|\) hran. Po přidání vrcholů \(u\) a \(v\) vede do \(S\) nejvýše \(3|S’|+4\) hran.
Pro počet hran \(\#e\) vedoucích do \(S\) tedy platí: \[ 3 (C_o(G,S)) \le \#e \le 3|S’|+4 \le 3 (C_o(G’,S’)-2)+4 = 3 (C_o(G,S))-2 \] což je hledaný spor.
