Minimum spanning tree. unique min edge vs non unique proof

2
votes

So I have an exercise that I should prove or disprove that:

1) if e is a minimum weight edge in the connected graph G such that not all edges are necessarily distinct, then every minimum spanning tree of G contains e

2) Same as 1) but now all edge weights are distinct.

Ok so intuitively, I understand that for 1) since not all edge weights are distinct, then it's possible that a vertex has the path with edge e but also another edge e_1 such that if weight(e) = weight (e_1) then there is a spanning tree which does not contain the edge e since the graph is connected. Otherwise if both e_1 and e are in the minimum spanning tree, then there is a cycle

and for 2) since all edge weights are distinct, then of course the minimum spanning tree will contain the edge e since any algorithm will always choose the smaller path.

Any suggestions on how to prove these two though? induction? Not sure how to approach.

1
algorithmgraphtreeproofminimum-spanning-tree
To disprove something, you just need to give a counterexample. It should be easy enough to find one for (1). Proving (2) is more involved. I find a good way is with proof by contradiction: Suppose that there is some graph G whose unique minimum-weight edge is not in any MST (remember that there could be more than one (unless you can prove otherwise)). If you can show how to change each of these "minimum" spanning trees into spanning trees of even lower weight, then you have shown a contradiction, i.e., that the unique min-weight edge must be in every MST of every graph. - j_random_hacker
@j_random_hacker now that I think about it wouldn't 1) only be disproven only if the graph doesn't contains a vertex such that the only path connecting it to another vertex is e? - john
When you say "such that not all edges are necessarily distinct" in your original question, you mean "such that not all edges necessarily have distinct weights", right? Every edge of course has a distinct identity from every other edge. - j_random_hacker
@j_random_hacker never mind I thought about this question wrong...so the statement was that generally all minimum spanning trees with min edge e *(not necessarily distinct) will contain e and I just disprove with a 3 vertex tree all connected to each other with the same weight. - john

1 Answers

0
votes

Actually in your first proof when you say that if both e and e_1 are in G, then there's a cycle, that's not true, because they're minimal edges, so there doesn't have to be a cycle, and you do need to include them both into the MST, because if |E| > 1 and |V| > 2 then they both have to be there.

Anyways, a counter example for the first one is a complete graph with all edges of the same weight as e, the MST will contain only |V|-1 edges, but you didn't include all the other edges of that same weight, hence you have a contradiction.

As for the second one, if all edges are distinct, then if you remove the minimum edge and want to reconstruct the MST, the only way to go about this is to add a an edge connecting the 2 disjoint sets that were broken up by that minimum-weight edge.

Now suppose that you didn't remove that minimum-weight edge, and added that other edge, now you've created a cycle, and since all edges are distinct the cycle-creating edge will be greater than all of them, hence if you remove any former MST edge from that cycle, it will only increase the size of the MST. Which means that pretty much all former MST edges are critical when all edges have distinct weights.