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.
My attempt :
The problem doesn't say that graph $G$ has distinct edges weights, so, if I assume graph $G$ has all are same edge weights. There, we have a counter example for $T'=T$; means MST may be different. For $T' \neq T$, assume graph $G$ has distinct edge weights. Similarly, we have some counter examples for $t'=t^2$ and also for $t'<t^2$. Hence, option $(4)$ should be correct.
But, the problem was from competitive exam GATE. GATE has marks to all for this question, means either there is no option matches or more than one options are matching.
Could you explain it, please?
I found an explanation:
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, $(2)$ is the general answer and $(1)$ is also true for a single edge graph. Hence, in GATE $2012$, marks were given to all.
Why is he proving true? Can we not find an counter example for given options?
He claims that all options $(1)$, $(2)$, and $(3)$ can be true?
Can I claim that all options $(1)$, $(2)$, and $(3)$ can be false?