1
$\begingroup$

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$)?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Rob32409
    Sep 26 at 18:59
  • $\begingroup$ Yes, that is indeed correct $\endgroup$
    – nir shahar
    Sep 26 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.