Multiple choice

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' = t2

  2. T' = T with total weight t' < t2
  3. T'$\ne$ T but total weight t' = t2

  4. None of these
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Graph G is counter example for options (2) and (3) and Graph G1 is counter example for option (1)

Keep practicing — related questions