Editing Minimum spanning tree (section)

==Properties==

===Possible multiplicity===
If there are {{mvar|n}} vertices in the graph, then each spanning tree has {{math|''n'' − 1}} edges.

[[File:Multiple minimum spanning trees.svg|thumb|This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.]]
There may be several minimum spanning trees of the same weight; in particular, if all the edge weights of a given graph are the same, then every spanning tree of that graph is minimum.

===Uniqueness===
''If each edge has a distinct weight then there will be only one, unique minimum spanning tree''. This is true in many realistic situations, such as the telecommunications company example above, where it's unlikely any two paths have ''exactly'' the same cost. This generalizes to spanning forests as well.

Proof:
# [[Proof by contradiction|Assume the contrary]], that there are two different MSTs {{mvar|A}} and {{mvar|B}}.
# Since {{mvar|A}} and {{mvar|B}} differ despite containing the same nodes, there is at least one edge that belongs to one but not the other.  Among such edges, let {{math|''e''{{sub|1}}}} be the one with least weight; this choice is unique because the edge weights are all distinct.  Without loss of generality, assume {{math|''e''{{sub|1}}}} is in {{mvar|A}}.
# As {{mvar|B}} is an MST, {{math|{''e''{{sub|1}}} ∪ ''B''}} must contain a cycle {{mvar|C}} with {{math|''e''{{sub|1}}}}.
# As a tree, {{mvar|A}} contains no cycles, therefore {{mvar|C}} must have an edge {{math|''e''{{sub|2}}}} that is not in {{mvar|A}}.
# Since {{math|''e''{{sub|1}}}} was chosen as the unique lowest-weight edge among those belonging to exactly one of {{mvar|A}} and {{mvar|B}}, the weight of {{math|''e''{{sub|2}}}} must be greater than the weight of {{math|''e''{{sub|1}}}}.
# As {{math|''e''{{sub|1}}}} and {{math|''e''{{sub|2}}}} are part of the cycle {{mvar|C}}, replacing {{math|''e''{{sub|2}}}} with {{math|''e''{{sub|1}}}} in {{mvar|B}} therefore yields a spanning tree with a smaller weight.
# This contradicts the assumption that {{mvar|B}} is an MST.

More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees.<ref>{{cite web|url=https://cs.stackexchange.com/q/2204 |title=Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?|website=cs.stackexchange.com|access-date=4 April 2018}}</ref>

===Minimum-cost subgraph===
If the weights are ''positive'', then a minimum spanning tree is, in fact, a minimum-cost [[Glossary of graph theory#Subgraphs|subgraph]] connecting all vertices, since if a subgraph contains a [[Path (graph theory)|cycle]], removing any edge along that cycle will decrease its cost and preserve connectivity.

===Cycle property===
''For any cycle {{mvar|C}} in the graph, if the weight of an edge {{mvar|e}} of {{mvar|C}} is larger than any of the individual weights of all other edges of {{mvar|C}}, then this edge cannot belong to an MST.''

Proof: [[Proof by contradiction|Assume the contrary]], i.e. that {{mvar|e}} belongs to an MST {{math|''T''{{sub|1}}}}. Then deleting {{mvar|e}} will break {{math|''T''{{sub|1}}}} into two subtrees with the two ends of {{mvar|e}} in different subtrees. The remainder of {{mvar|C}} reconnects the subtrees, hence there is an edge {{mvar|f}} of {{mvar|C}} with ends in different subtrees, i.e., it reconnects the subtrees into a tree {{math|''T''{{sub|2}}}} with weight less than that of {{math|''T''{{sub|1}}}}, because the weight of {{mvar|f}} is less than the weight of {{mvar|e}}.

===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.

===Minimum-cost edge===
''If the minimum cost edge {{mvar|e}} of a graph is unique, then this edge is included in any MST.''

Proof: if {{mvar|e}} was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding {{mvar|e}} to the MST, would yield a spanning tree of smaller weight.

===Contraction===
If {{mvar|T}} is a tree of MST edges, then we can ''contract'' {{mvar|T}} into a single vertex while maintaining the invariant that the MST of the contracted graph plus {{mvar|T}} gives the MST for the graph before contraction.<ref name=PettieRamachandran2002/>