# Squaring the weights of an undirected graph and minimum spanning trees

This is from question 3(a) from http://www.cs.cmu.edu/afs/cs/academic/class/15210-s14/www/exams/exam2-practice-sol.pdf, which is: consider an undirected graph $$G$$ with unique positive weights. Suppose it has a minimum spanning tree $$T$$ . If we square all the edge weights and compute the MST again, do we still get the same tree structure? The answer says that it is true so I'm trying to prove it, but I'm quite stuck. I have only written the following. By contradicion, let $$T'\neq T$$ be MST of the graph $$G$$ with the squared weights. Then \begin{align*} \sum_{i\in T'}w_i^2 < \sum_{i\in T}w_i^2 \end{align*} how can arrive at a contradiction (for example, $$\sum_{i\in T'}w_i < \sum_{i\in T}w_i$$)?

Hint: how does Kruskal's algorithm work? What can you say about the execution of Kruskal on the new graph?

• I think I got it. So, nothing will change in the execution of Kruskal's algorihtm because $x^2$ is an increasing function for $x>0$. Is this correct? Sep 26 at 18:59
• Yes, that is indeed correct Sep 26 at 19:16