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.)

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