Graf s n kostrami
Úloha číslo: 4083
Pro která \(n\) existuje graf s právě \(n\) různými kostrami?
Řešení
Pro \(n=1\) lze vzít libovolný strom, to jsou grafy s právě jednou kostrou.
Pro \(n\ge 3\) lze vzít cyklus \(C_n\).
Prostý graf s právě dvěma kostrami neexistuje – musel by mít alespoň jeden cyklus, a tedy alespoň tři kostry.
(Kdybychom dovolili násobné hrany, pak takový graf existuje – stačí vzít strom a v něm zdvojit libovolnou hranu.)