Editing Minimum spanning tree (section)

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