Let $G$ be a weighted graph with edge weights greater than one and $G'$ be…

PYQ GATE 2012Modified — slightly modified from the official paper; see the solution

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?

Assume G is connected and undirected, has at least three vertices, and has pairwise distinct edge weights.

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 219 students.

Explore the full course: Algorithms

Let \(G\) be a weighted graph with edge weights greater than one and \(G'\) be…