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.

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?

  • $\begingroup$ The problem says, "the minimum spanning trees," which may mean you are supposed to assume that each graph has a unique minimum spanning tree. $\endgroup$ – Gerry Myerson Jan 28 '16 at 8:21
  • $\begingroup$ @GerryMyerson , can the decide distinguish weight of graph? $\endgroup$ – 1 0 Jan 18 '18 at 10:51
  • $\begingroup$ Sorry, I don't understand what you are asking. $\endgroup$ – Gerry Myerson Jan 18 '18 at 18:08

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

  • $\begingroup$ We need to find the counter example for the options $(1) , (2), \text{and} (3)$. Which can be show. $\endgroup$ – 1 0 Dec 25 '15 at 8:39
  • $\begingroup$ correct, there are counterexamples to all of them, so is the answer (4)? Or is the question "Which of the following could be true?" $\endgroup$ – Forever Mozart Dec 25 '15 at 8:41
  • $\begingroup$ Option $(4) \text{None of the above}$ should be correct, but GATE has given marks to all. Why? $\endgroup$ – 1 0 Dec 25 '15 at 8:43
  • $\begingroup$ Ah, (3) could be true if $G$ is, say, two vertices with multiple edges between them, and all have the same weight. $\endgroup$ – Forever Mozart Dec 25 '15 at 8:45
  • $\begingroup$ So any one of them could be true. Since all received points, this must be what the question was asking. $\endgroup$ – Forever Mozart Dec 25 '15 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.