Let \(G\) be a weighted graph with edge weights greater than one and \(G'\) be…
2012
Let \(G\) be a weighted graph with edge weights greater than one and \(G'\) be the graph constructed by squaring the weights of edges in \(G\). Let \(T\) and \(T'\) be the minimum spanning trees of \(G\) and \(G'\), respectively, with total weights \(t\) and \(t'\). Which of the following statements is TRUE?
- A.
\(T' = T\)with total weight\(t' = t^2\) - B.
\(T' = T\)with total weight\(t' < t^2\) - C.
\(T' \neq T\)but total weight\(t' = t^2\) - D.
None of the above
Attempted by 128 students.
Show answer & explanation
Correct answer: D
T' = T always: Squaring weights (>0) preserves edge order (strictly increasing function), so Kruskal/Prim selects same edges.
t' vs t²: t = Σ w_i, t' = Σ w_i². By expansion, t² = t' + 2Σ_{i<j} w_i w_j ≥ t'.
= if |V|=2 (1 edge): t' = t² (A true).
< if |V|≥3 (≥2 edges): t' < t² (B true).
C false: T' = T, so ≠ can't hold.
General graph (any |V|): No option always true → D.
Example (|V|=3): Edges 1,2,4. MST sum t=3, t'=1+4=5<9. B holds, but not universal.
A video solution is available for this question — log in and enroll to watch it.