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.

Obtížnost: Obtížná úloha
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
Komplexní úloha
En translation
	Zaslat komentář k úloze