Kubické grafy

Úloha číslo: 3819

Dokažte, že pro každý kubický (t.j. 3-regulární) graf \(G\) platí, že \(k_v(G)=k_e(G)\).

  • Řešení

    Víme, že \(k_v(G) \le k_e(G)\).

    Rovnost stačí rozebrat podle rostoucí vrcholové souvislosti \(k_v(G)\).

    Pokud je \(k_v(G)=1\), má \(G\) artikulaci. Po jejím odebrání se graf rozpadne na alespoň dvě komponenty. Protože má artikulace stupeň 3, do alespoň jedné z těchto komponent vede právě jedna hrana, neboli \(k_e(G)=1\).

    Podobně postupujeme, pokud má \(G\) dvouvrcholový řez \(\{u,v\}\). Podle stejného argumentu jako v předchozím případě, vede z \(u\) do jedné z komponent \(C\) právě jedna hrana. Pokud do \(C\) vede z \(v\) jedna hrana, máme hledaný řez. Jinak vedou z \(v\) do \(C\) dvě hrany, \(G\) má po odebrání \(\{u,v\}\) dvě komponenty \(C,C'\) a \(u\) a \(v\) nejsou spojeny hranou. Hrany mezi \(u\) a \(C\) a mezi \(v\) a \(C'\) tvoří hledaný řez.

    Minimální stupeň je horní mez na hranovou i vrcholovou souvislost, proto v ostatních případech zůstanou grafy vrcholově i hranově třísouvislé.

  • Varianta

    Ukažte, že každý bipartitní kubický souvislý graf je nutně vrcholově 2-souvislý.

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