Existence kostry

Úloha číslo: 4079

Ukažte, že každý souvislý graf má kostru.

  • Řešení

    Indukcí podle počtu hran:

    Je-li \(G\) strom, je sám sobě kostrou.

    Je-li souvislý a není strom, potom obsahuje hranu \(e\), že \(G-e\) je souvislý. Podle indukčního předpokladu má \(G-e\) kostru, která je i kostrou \(G\).

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