0
$\begingroup$

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:

  1. Assume the contrary, that there are two different MSTs A and B.
  2. Since A and 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 e1 be the one with least weight; this choice is unique because the edge weights are all distinct. Without loss of generality, assume e1 is in A.
  3. As B is an MST, {e1} ∪ B must contain a cycle C with e1.
  4. As a tree, A contains no cycles, therefore C must have an edge e2 that is not in A.
  5. Since e1 was chosen as the unique lowest-weight edge among those belonging to exactly one of A and B, the weight of e2 must be greater than the weight of e1.
  6. As e1 and e2 are part of cycle C, replacing e2 with e1 in B therefore yields a spanning tree with a smaller weight.
  7. This contradicts the assumption that B is an MST.

Question: Can't we just skip adding e1 to B and just get the smallest edge from B, and state that e1 < e2, since all edges are unique? Thus, it implies that there is only one MST possible.

Improve this question
$\endgroup$
4
  • $\begingroup$ You refer to a "telecommunications company example above" but your question contains no such example. Also please cite the source of all copied material. $\endgroup$
    – Steven
    Oct 5 at 14:07
  • $\begingroup$ Please do not delete your question after receiving an answer. This is often considered impolite. Part of our purpose here is to build up an archive of high-quality questions and answers that will be useful to others -- not just to you -- and answerers may be writing their answer on the assumption that it will help not only you but others. $\endgroup$
    – D.W. ♦
    Oct 13 at 19:04
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/162340/755, stackoverflow.com/q/77236342/781723. Please do not post the same question on multiple sites. $\endgroup$
    – D.W. ♦
    Oct 13 at 19:05
  • $\begingroup$ I’m voting to close this question because it was cross-posted. $\endgroup$
    – D.W. ♦
    Oct 13 at 19:05

1 Answer 1

Reset to default
1
$\begingroup$

If $e_2$ is the lightest edge from $B$ then the weight of $e_2$ could be smaller than the weight of $e_1$ (when $e_2$ also belongs to $A$).

Even if such $e_2$ was in $B$ but not in $A$ and had a larger weight than $e_1$ (which is implied from the choice of $e_1$), this still doesn't prove that you can get a lighter MST by replacing $e_2$ with $e_1$ since $(B \setminus \{e_2\}) \cup \{e_1\}$ might be a disconnected graph with two connected components: a tree, and a unicyclic graph.

However, if you choose $e_2$ as the heaviest edge of the unique cycle of $B \cup \{e_1\}$ (which cannot be $e_1$ itself), then $(B \setminus \{e_2\}) \cup \{e_1\}$ is necessarily a tree, and this tree must be lighter $B$.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.