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**?

- $T' = T$ with total weight $t' = t^2 $
- $T' = T$ with total weight $t' < t^2$
- $T' \neq T$ but total weight $t' = t^2$
- None of the above

### 9 Comments

Or atleast they could have mentioned t and t' are only (unique) MST possible on the graph G and G', then option B would be correct.

Its this sort of questions which waste lot of time of candidates in exam, also break their confidence a bit.

@Arjun sir,

Can we consider two tree equivalent even when they have different weighted edges but are isomorphic to each other ?

So here equality means isomorphism ?

## 5 Answers

$t'$ < $t^2$, because sum of squares is always less than the square of the sums except for a single element case.

Hence, B is the general answer and A is also true for a single edge graph. Hence, in GATE 2012, marks were given to all.

### 23 Comments

None of the above would mean all others are false rt? Or the question should have asked "Always TRUE". Here is the answer key same file as published by IIT-K.

http://gatecse.in/w/images/b/b5/Key_CS_2012.pdf

This official site supposedly still has the key. But as usual no words for IIT IT department.

@ Pragy Agarwal Sir, How option C can be true.. Please give an example... Even in case of multiple MSTs, although T and T' may be different but still t' will not be equal to t^{2} in any case. Please clarify