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