Suppose G is an undirected connected weighted graph such tha

Suppose G is an undirected, connected, weighted graph such that the edges in G have distinct positive edge weights. Show that the minimum spanning tree for G is unchanged even if we square all the edge weights in G, that is, G has the same set of edges in its minimum spanning tree even if we replace the weight, w(e), of each edge e in G, with w(e)^2.

Solution

Suppose for weights w(e) let minimum spanning tree be S1,let the tree with same edges as S1 but weights squared is S2. Now if the minimum spanning tree for weights w(e)^2 is P2, let the P1 be the tree with square roots of weights of P2. As P2 is minimum spanning tree, P1 also must alteast be a spanning tree. Now we know for graph with unsquared weights we know that S1 is minimum spanning tree, so if P1 is not S1 then the sum of all the weights in P1 must be greater than sum of all the weights in S1. Which implies that sum of all the weights in P2 must be greater than sum of all the weights in S2, because it is already given that all the weights are positive. So if P2 is minimum spanning tree, then it has to be S2.