Comments on Homework 2:

Exercise 3, Part 2.

-The most common mistake was to assume that the graph G has a unique
 minimal spanning tree T*. Note that there are lots of graphs G that
 have multiple minimal spanning trees, including the graph G from part
 1. Many students tried to argue that if F is contained in T*, and e
 is a minimal cost edge in the cut of the component U, then Fu{e} is
 also contained in T*. Since not all connected graphs G have a unique
 MST, this argument does not work for all G.

-There were several arguments involving "swapping" the edge e. In
 order to get full points, you need to be specific about how you are
 swapping. Just because there is no better edge in the cut to "swap" e
 with, doesn't immediately imply that Fu{e} is contained in a MST. You
 need to argue that if F is contained in a minimal spanning tree T,
 then Fu{e} is contained in some minimal spanning tree T', where
 either T'=T or else T' is obtained from T by swapping an edge in T
 with the edge e.

-Another mistake was to use the correctness of Prim's algorithm to
 prove this part. Note that part 3 is to prove the correctness of
 Prim's algorithm using part 2, so it would be circular logic to use
 part 3 to prove part 2.

Exercise 3, Part 3.

A common mistake was to repeat the same "swapping" argument mentioned
above. Again, note that just because there is no better edge in the
cut to "swap" e with, doesn't immediately imply that the algorithm
outputs a spanning tree with the minimal cost out of all possible
spanning trees.  Since the problem tells you to use part 2, your
argument should say something about greedy forests/trees.