Editing Minimum spanning tree (section)

===Cut property===
[[File:Msp-the-cut-correct.svg|thumb|400px|This figure shows the cut property of MSTs. {{mvar|T}} is the only MST of the given graph. If {{math|1=''S'' = {''A'',''B'',''D'',''E''},}} thus {{math|1=''V'' – ''S'' = {''C'',''F''},}} then there are 3 possibilities of the edge across the cut {{math|(''S'', ''V'' – ''S'')}}, they are edges {{mvar|BC}}, {{mvar|EC}}, {{mvar|EF}} of the original graph. Then, e is one of the minimum-weight-edge for the cut, therefore {{math|''S'' ∪ {''e''} }} is part of the MST {{mvar|T}}.]]

''For any [[cut (graph theory)|cut]] {{mvar|C}} of the graph, if the weight of an edge {{mvar|e}} in the cut-set of {{mvar|C}} is strictly smaller than the weights of all other edges of the cut-set of {{mvar|C}}, then this edge belongs to all MSTs of the graph.''

Proof: [[Reductio ad absurdum|Assume]] that there is an MST {{mvar|T}} that does not contain {{mvar|e}}. Adding {{mvar|e}} to {{mvar|T}} will produce a cycle, that crosses the cut once at {{mvar|e}} and crosses back at another edge {{mvar|e'}}. Deleting {{mvar|e'}} we get a spanning tree {{math|''T''∖{''e' ''} ∪ {''e''} }} of strictly smaller weight than {{mvar|T}}. This contradicts the assumption that {{mvar|T}} was a MST.

By a similar argument, if more than one edge is of minimum weight across a cut, then each such edge is contained in some minimum spanning tree.