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?
Best Answer
(1) is true iff $G=K_2$. (although, maybe empty graph and $K_1$ would trivially satisfy this?)
(2) would be true if, say, $G$ is a tree with at least two edges.
(3) I do not think could ever be true. Two different spanning trees would mean $G$ has at least two edges, and the sum of squares of at least two numbers $\geq 1$ is never equal to the square of the sum.
I'm not sure how you should answer the question, but that's my understanding of the problem.