1. (10 pts) Let G = (V,E) be a graph with an edge-weight function w, and let the tree T ? E be a minimum spanning tree on G. Now, suppose that we modify G slightly by decreasing the weight of exactly one of the edges in (x, y) ? T in order to produce a new graph G?. Here, you will prove that the original tree T is still a minimum spanning tree for the modified graph G?.

To get started, let k be a positive number and define the weight function w? as

w'(u,v) =

w(u,v) if (u,v) != (x,y)

and

w'(u,v)=

w(x,y)?k if(u,v)=(x,y) .

Now, prove that the tree T is a minimum spanning tree for G?, whose edge weights are given by w?.