GATE CSE 2012 | Question: 29

Question

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

Comments

T and T' will be same

If G has duplicate weights, then T itself is not unique

t' <= t^2

---

Thanks  brother,  I got it 👍 😄, problem with my statement.

---

@Honey badger

There is nothing wrong with your comment. It is correct. I added my comment independently. 

Regarding the inequality : t' = t^2 for single edge graph between two vertices. Otherwise t' will always be less than t^2 

Answer 1

T and T' can be diffrent because MST need not be unique suppose there are 2 edges with same weight then we can draw different MST's if in question it would have been given distinct weight then ofocurse T = T' but since not mentioned T may not be equal T'

2 . sum of squares is always less than squared sum of numbers ( 1 + 2 + 3 ) **2 = 36 > 1**2  + 2**2 + 3**2 = 36 > 13 so t' < t**2

Since no option matches given answer is D