Mosty v kostře
Úloha číslo: 4080
Ukažte, že každá kostra obsahuje všechny mosty, t.j. hrany, jejichž odebráním se stane graf nesouvislý.
Řešení
Kdyby existoval most \(e\) a k němu kostra \(K\) taková, že \(e\notin K\), potom by přidáním \(e\) do \(K\) vznikla kružnice.
Následně by i po odebrání \(e\) graf zůstal souvislý, což je spor s tím, že \(e\) je most.