(a) Let T be a minimum spanning tree of a weighted graph G. Construct a new graph G by adding a weight of k to every edge of G. Do the edges of T form a minimum spanning tree of G ? Prove the statement or give a counterexample.
(b) Let P = {s, . . . , t} describe a shortest weighted path between vertices s and t of a weighted graph G. Construct a new graph G by adding a weight of k to every edge of G. Does P describe a shortest path from s to t in G ? Prove the statement or give a counterexample.