Cut property
For a connected graph G = (V, E),
Given that S is a non-empty subset of V,
let e = {v, w} be the minimal cost edge between S and V-S.
Then we say that every MST contains e.
Proof
Suppose there exists an minimum spanning tree without the edge e connecting {v, w}.
There must exist another edge which crosses the cut, e2 (By definition of a MST).
There must also exist a path from v to w, creating a cycle in T ∪ {e}.
Follow the path to find a different edge that goes from S to S-V.
Let that be e’. Remove it from T ∪ {e} to get T’
Hence it is shown that T’ is a spanning tree with a lower cost than T.