Prove that if all its edge weights are distinct, then it has a unique minimum spanning tree
Answers
Answered by
0
we have an algorithm that finds an MST (which we will call A) based on the structure of the graph and
the order of the edges when ordered by weight.
2. Assume MST A is not unique.
3. There is another spanning tree with equal weight, say MST B.
4. Let e1 be an edge that is in A but not in B.
5. Then B should include at least one edge e2 that is not in A.
6. Assume the weight of e1 is less than that of e2.
7. As B is a MST, {e1} B must contain a cycle.
8. Replace e2 with e1 in B yields the spanning tree {e1} B - {e2} which has a smaller weight compared to B.
9. Contradiction. As we assumed B is a MST but it is not.
the order of the edges when ordered by weight.
2. Assume MST A is not unique.
3. There is another spanning tree with equal weight, say MST B.
4. Let e1 be an edge that is in A but not in B.
5. Then B should include at least one edge e2 that is not in A.
6. Assume the weight of e1 is less than that of e2.
7. As B is a MST, {e1} B must contain a cycle.
8. Replace e2 with e1 in B yields the spanning tree {e1} B - {e2} which has a smaller weight compared to B.
9. Contradiction. As we assumed B is a MST but it is not.
Similar questions