5. (7 points) A traveling salesperson (Traveler) and taxicab driver (Driver) are having an argument about MST algorithms. Traveler says that Prims algorithm might return the wrong answer if any of the edge weights are negative, but Driver disagrees. Traveler proposes the following algorithm to find an MST T in a weighted graph G if there are any negative edges weights: First, find the minimum edge weight among the edges in G; call it w (so, w is the negative number of largest magnitude). Next, add |w | to all the edge weights, forming a new graph G0 . Finally, run Prims algorithm on G0 and return the resulting MST T 0 .

(a) Traveler and Driver dont know if T 0 is equal to T. Is it possible to conclude that T 0 is equal to T? Explain your answer.

(b) Driver claims that this whole exercise is a waste of time because Prims algorithm is correct even if there are negative edge weights. Is Driver right?