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

we can make different as well as same MST also so option (d) is correct option

Comments

D IS MORE CORRECT THAN B

Answer 2

Here is the solution : 

Comments

T' != T suppose we have same repeated edges in that case we can have multiple mst possible for both graphs hence T' will be not equal to T and for t' < t^2 or t' > t^2 depends on the weights

---

Thank You

---

How you can pick edge weight= 1, because its clearly given in the question edge weight can not be 1

Answer 3

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'

Comments

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

so why not ans B.

---

When edge weights are all equal then T and T' may not be equal

---

2nd can also be of the same form as the first one 
both of them can be made similar

 

Answer 4

We are given:

 

# A weighted graph G where all edge weights are greater than one.

# A transformed graph G′ where each edge weight in G is squared.

# T is the Minimum Spanning Tree (MST) of G with total weight t.

# T′ is the MST of G′ with total weight t′.

 

Step 1: How Squaring Affects Edge Weights

# Suppose G has edge weights w1 ,w2 ,…,wm.

# In G′, each weight is squared:   w1², w2², w3², … , wm²

# Since all edge weights are greater than one, squaring increases their values

(i.e., w² > w for w>1).

 

Step 2: Does the Same MST Structure Hold?

# In Kruskal’s algorithm, edges are picked in increasing order of weight.

# When we square weights, the relative order between small and large edges might change.

Example: If w1 < w2 , squaring might increase their gap (e.g., 2²=4 and 3² =9).

This means the set of edges selected in T might change in T′.

 

Conclusion:

T and T′ might be different because squaring can alter the priority of edges.

Thus, T′ ≠ T in general.

 

Step 3: What Happens to Total Weight?

Incorrect Claim: t′= t²

Why? The MST weight is the sum of selected edge weights, but

w1² + w2² + ⋯ + wn² ≠ (w1 +w2 +⋯+wn) ²

 

Conclusion: t′≠ t², meaning options A and C are false.

 

Step 4: Is t′ < t² ?

Since all edge weights increase when squared,

The weight of the MST must increase, meaning t′>t.

However, t′ is not necessarily less than t².

This means option B is also incorrect.

 

Final Conclusion:

Since none of the options A, B, or C hold, the correct answer is option D: None of the above.

Answer 5

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.

Comments

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

Answer 6

Answer is D.

Take a complete graph with 3 vertices and each edge is 2. So if we square all, we still can have different types of mst than previous with same cost. Since all options are comparing T and T', they're all wrong, as we can't say. T and T' may or may not be equal. Hence D.