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.


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.