Formulujte větu o trhání listů. Dále formulujte alespoň jednu vlastnost stromů ekvivalentní s

definicí stromu.

Věta o trhání listů

Odebrání listu

• Uvažujme strom G = (V,E), ve kterém existuje list v

→ označme w jeho souseda v G ⇒ pak odebráním listu v z G je operace kterou vznikne graf G − v = (V \ {v}, E \ {{w, v}})

Přídání listu

• Uvažujme strom G = (V,E) a zvolme w ∈ V

→ Pak přidání listu v k vrcholu w, v !∈ V , ke grafu G je operace, kterou vznikne graf G + v = (V ∪ {v}, E ∪ {{w, v}}).

Věta o trhání listů

Nechť G = (V,E) je graf na alespoň dvou vrcholech a nechť v ∈ V je jeho list.

⇒ následující tvrzení je ekvivalentní: