12,736 views

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?

1. $T' = T$ with total weight $t' = t^2$
2. $T' = T$ with total weight $t' < t^2$
3. $T' \neq T$ but total weight $t' = t^2$
4. None of the above

@Arjun Sir, @srestha ma'am,

For such a question, What should we opt for option B or D

Isn't that clearly mentioned in the answer?
edited

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

When the edge weights are squared the minimum spanning tree won't change.

$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.
by

How is option A correct for single edge graph since edge weight has to be >1?
edited
In question they didn’t mention distinct edges.

If I assume all edge weights as same then either $T' = T$ or $T' \neq T$ but $t' < t^2$.

@gatecse and @arjun sir

When the edge weights are squared the minimum spanning tree won't change.

This line is only true when we consider only positive edge weights, right?  we can make different as well as same MST also so option (d) is correct option

by

### 1 comment

D IS MORE CORRECT THAN B
d will be the answer. t' may or may not b equal to t . if distict weight it will be equal and if same weight then diffrent structure may be obtained . plus the weight of t <= t'
by

### 1 comment

Can you Explain why T and T' are not equal and t'<t^2.

so why not ans B.
Here D is correct. As everyone said B option is true but in one case it fails if there is a graph with 2 Nodes and edge weight is 1 then it t1==t^2, thus t1<t^2 will fail. And definitely MST doesn't change When edge weights are squared.
by

edited
@PRG1499 But in the question it is given that edge weights should be greater than one.
Yes, but we can get a different structure from 2 edges having the same value, thus option B fails atleast one test case.