1
$\begingroup$

Here's what I have so far:

Let us assume that there's another minimum spanning tree, t2, other than tree t1. This means that the sum of weights of both trees are the same. Let there be an edge e that's in t1, but not in t2. This means that there has to be an edge f that is present in t2, and not in t1, as both minimum spanning trees must have V edges. There is no way that the weight of e and f are the same, as the given graph has distinctly weighted edges. This means that the two trees don't have the same total weight. Thus they cannot be the same minimum spanning tree.

I was just wondering if this proof is complete and doesn't have any holes in it.

$\endgroup$
  • $\begingroup$ What if the two spanning trees differ in more than one edge? You are on the right track, to a large extent, but your argument is not complete. $\endgroup$ – Fabio Somenzi Dec 3 '18 at 16:45
  • $\begingroup$ I have no idea how to proceed if there's more than one differing edge. Could you give me another small hint? $\endgroup$ – pinklemonade Dec 3 '18 at 16:53
  • $\begingroup$ Consider the edge of maximum weight among those that are in one spanning tree but not in the other. What happens if you remove it from its tree? Can you replace it? $\endgroup$ – Fabio Somenzi Dec 3 '18 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.