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

@Arjun Sir, @srestha ma'am,

For such a question, What should we opt for option B or D? 
Please Clarify.

---

Isn't that clearly mentioned in the answer?

---

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

Answer 1

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.