GATE CS 2010 Q50 — Minimum Spanning Trees

Since vertex $0$ must be a leaf in the spanning tree $T$, its degree in $T$ is exactly $1$. Removing vertex $0$ and its single incident edge must leave a spanning tree $T'$ on the remaining vertices $\{1, 2, 3, 4\}$.

To minimize the total weight of $T$, we can decompose the problem into two independent steps:

1. Find the Minimum Spanning Tree (MST) of the subgraph induced by the vertices $\{1, 2, 3, 4\}$.
2. Connect vertex $0$ to this MST using the edge of minimum weight incident on $0$.

Step 1: MST of the subgraph on $\{1, 2, 3, 4\}$
Using Kruskal's algorithm, we sort the edges of the subgraph by weight:

• Edge $\{3, 4\}$ with weight $2$ (Selected)
• Edge $\{2, 4\}$ with weight $3$ (Selected)
• Edge $\{1, 3\}$ with weight $4$ (Selected)

Step 2: Connect vertex $0$
The weights of the edges incident on vertex $0$ are $W_{01} = 1$, $W_{02} = 8$, $W_{03} = 1$, and $W_{04} = 4$.
The minimum weight edge incident on $0$ has weight $\min(1, 8, 1, 4) = 1$ (using either $\{0, 1\}$ or $\{0, 3\}$).

Thus, the minimum possible weight of the spanning tree $T$ is: $$\text{Total Weight} = 9 + 1 = 10$$