GATE CS 2012 Q29 — Minimum Spanning Trees

1. Minimum Spanning Tree ($T' = T$):

Since the edge weights of $G$ are greater than $1$, the squaring function $f(x) = x^2$ is strictly monotonic (increasing) for all $x > 1$. Any MST algorithm (such as Kruskal's or Prim's) relies solely on the relative order of edge weights. Since the relative order of weights remains unchanged in $G'$, the set of edges selected for the minimum spanning tree remains identical. Thus, $T' = T$.

2. Total Weight Comparison ($t'$ vs $t^2$):

Let the edges of the MST $T$ have weights $w_1, w_2, \dots, w_k$, where $k = n-1$ is the number of edges in the MST.

• The total weight of $T$ is $t = \sum_{i=1}^{k} w_i$.
• The total weight of $T'$ is $t' = \sum_{i=1}^{k} w_i^2$.

Expanding $t^2$, we get:

Since all $w_i > 1$:

• If the graph has only $2$ vertices ($k = 1$ edge), then there are no cross-terms, giving $t' = t^2$.
• If the graph has $3$ or more vertices ($k \ge 2$ edges), the cross-terms are strictly positive, giving $t' < t^2$.

Conclusion:

Because the number of vertices in $G$ is not specified, the relationship between $t'$ and $t^2$ depends on the graph size. Due to this ambiguity, GATE declared this question as Marks to All (MTA), represented here by option X.