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.