Vynechání hrany v kubickém grafu

Úloha číslo: 3265

Nechť \(G\) je kubický graf bez mostů. Dokažte, že pro každou jeho hranu existuje perfektní párování, které ji neobsahuje.

  • Nápověda

    Odeberte hranu z grafu a zkotrolujte Tutteho podmínku, např. sporem.

    Všimněte si, že z lichých komponent vedou alespoň 3 hrany.

  • Ř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\).

    Když odebereme hranu \(e\), budeme pro spor předpokládat, že \(G-e\) 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-e,S)\).

    Pokud měla \(e\) oba konce v \(S\) nebo oba konce v některé komponentě, platí \(C_o(G,S)=C_o(G-e,S)\) a dostaneme spor okamžitě. Nutně tedy \(e\) spojuje dvě liché komponenty \(G-e\). Z nich se stane vrácením \(e\) jedna sudá v \(G\). Tudíž \(C_o(G-e,S)=C_o(G,S)+2\).

    Tyto dvě komponenty jsou spojeny nejen mezi sebou hranou \(e\), ale jsou také spojeny s řezem \(S\). Protože v grafu \(G-e\) jde o liché komponenty, má do nich podle principu sudosti vést lichý počet hran. Protože graf \(G\) nemá mosty, vycházejí z každé liché komponenty (v \(G\) i v \(G-e\)) alespoň tři hrany. Podobně do sudých komponent vedou alespoň dvě hrany. Tudíž do spojené komponenty v \(G\) vedou alespoň čtyři hrany a celkem do \(S\) alespoň \(3 C_o(G,S)+4\) hran.

    Naopak, v \(G-e\) platí \(|S| < C_o(G-e,S)\). Obě strany jsou celá čísla, proto platí i \(3|S| < 3 C_o(G-e,S)-2\).

    Protože \(G\) je kubický, vede do \(S\) nejvýše \(3|S|\) hran. Pro počet hran \(\#e\) vedoucích do \(S\) v grafu \(G\) tedy platí: \[ 3 C_o(G,S)+4 \le \#e \le 3|S| < 3 C_o(G-e,S)-2 = 3 (C_o(G,S)+2) -2 =3 C_o(G,S)+4, \] což je hledaný spor.

Obtížnost: Obtížná úloha
Úloha na dokazování, ověřování
Komplexní úloha
En translation
	Zaslat komentář k úloze