Sbírka matematických úloh

Předepsaná hrana v kubickém grafu

Úloha číslo: 3266

• 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.