DAA#MST

Question

what is cut property of minimum spanning tree .?? can somone give an example.

Comments

u mean cut vertex and cut set?

---

No..  It is different from cut vertex and cut set.

---

Let $X \subseteq E$ be a part of $MST$ of $G(V,E)$,  $S \subseteq V$ be such that no edge of $X$ crosses

between $S$ and $V-S$, and $e \ \epsilon \ E$ be the lightest edge across this partition.

Then $X + \left \{ e \right \}$  is a part of some $MST$

Answer 1