308-360 Tutorial #4

Question 2

Edges listed in order added to MST:

- (c,e)
- (a,e)
- (c,h)
- (e,g)
- (d,f)
- (d,h)
- (b,h)

Yes. For example, we could have chosen edge

Question 3: Let (u,v) be a minimum-weight edge in a graph G. Show that
(u,v) belongs to some minimum spanning tree of G.

Let *S* be the set of all MST. Assume there exists an edge *e = (u,v)* of minimum weight s.t. *e* is not in T for all T in S. This implies that *e* was never picked as a safe edge. When the algorithm is considering *e* to be added to the growing tree, it was never picked for any MST. The algorithm always pick the edge with smallest weight across the cut. This implies that there exists an edge *e'* s.t. *w(e') < w(e)*. Contradiction.

current vertices not in MST yet MST | e ----|------- | | e' ----|------- | | ----|------- | |

Question 4

**Prove that if all edges in a graph have different weight then there is only one MST.**

Let *w _{1}*,

Sufficient: Distinct edge weights => unique MST?

Yes. Proved above.

Necessary: Is it necessary to have distinct edge weights in order to have a unique MST. In other words: Not distinct weights => Not unique MST. Or equivalently: Unique MST => Distinct edges.

So, is it a sufficent necessary condition for a unique MST? No. Here is a counter example:

1 3 1 G *-------*--------*-------* MST of G is: 1 3 1 *-------*--------*-------*