GATE CS 2016 Set 1 Q39 — Minimum Spanning Trees

To find the maximum possible weight of a minimum spanning tree (MST) of $G$, we want to assign the edge weights $1, 2, 3, 4, 5,$ and $6$ to the complete graph $K_4$ in a way that forces Kruskal's algorithm to choose larger weights.

Let the sorted weights of the edges be $e_1 < e_2 < e_3 < e_4 < e_5 < e_6$ with weights $1, 2, 3, 4, 5, 6$ respectively.

1. Kruskal's algorithm will always select the edge of weight $1$ ($e_1$).
2. It will then select the edge of weight $2$ ($e_2$), as two edges cannot form a cycle.
3. To maximize the MST weight, we must force the algorithm to reject the edge of weight $3$ ($e_3$). This is only possible if the edges with weights $1, 2,$ and $3$ form a cycle (a triangle) on three vertices, say $v_1, v_2,$ and $v_3$.

With $v_1, v_2, v_3$ forming a triangle, the fourth vertex $v_4$ must connect to this component. The edges incident to $v_4$ are connected to $v_1, v_2,$ and $v_3$, and their weights must be a permutation of the remaining weights: $4, 5,$ and $6$.

To connect $v_4$ to the spanned component, Kruskal's algorithm will choose the minimum weight edge incident to $v_4$, which is the edge of weight $4$.

Thus, the edges selected for the MST will have weights $1, 2,$ and $4$.
$$\text{Maximum possible weight of MST} = 1 + 2 + 4 = 7$$