308-360 Tutorial #4

Question 2

Edges listed in order added to MST:

  1. (c,e)
  2. (a,e)
  3. (c,h)
  4. (e,g)
  5. (d,f)
  6. (d,h)
  7. (b,h)
Is there more than one MST?

Yes. For example, we could have chosen edge (a,c) instead of (a,e). Both are of same weight. More on this in Q3 and Q4.

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
         |   e
         |   e'

Question 4

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

Let w1, w2, ..., w|E| be the weights. If wi <> (not equal) wj for all i <> j then there exists an unique ordering of the weights. (For any numbers x, y only one of the following holds: x = y, x < y or x > y). Edges are sorted by weights and processed by increasing weight by the algorithm. A unique ordering of the weights implies that the algorithm has no choice, it can process the edges only in a unique way and this gives the unique MST.

Is it a sufficent necessary condition for a unique MST?

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