Počet koster 2-souvislých grafů

Úloha číslo: 3822

Dokažte, že každý vrcholově 2-souvislý graf na \(n\) vrcholech má alespoň \(n\) koster. Kdy nastává rovnost?

  • Řešení

    Indukcí podle počtu vrcholů, přidáváním uší.

    Pro cyklus platí rovnost.

    Vznikne-li grafu \(G\) odebráním ucha s \(t\) vrcholy graf \(G'\), potom každou kostru \(G'\) lze rozšířit \(t+1\) způsoby na kostru \(G\) a to tak, že do kostry přidáme celé ucho až na jednu hranu. (Graf \(G\) může mít ještě jiné kostry obsahující celé ucho.)

    Z nerovností \(\kappa(G)\ge (t+1)\kappa (G')\) a \(\kappa(G')\ge |V(G')|\) už výsledek plyne přímočaře.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze