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.

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