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$)?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Hint: how does Kruskal's algorithm work? What can you say about the execution of Kruskal on the new graph?
answered Sep 26, 2021 at 18:17
-
$\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$– Rob32409Commented Sep 26, 2021 at 18:59
-