GATE CS 2018 Q47 — Minimum Spanning Trees

In the given undirected graph $G$, the vertices are $a, b, c, d, e$ with the following edge weights:

• Weight 1: $(a, e)$ and $(d, e)$
• Weight 2: $(a, b)$, $(c, d)$, and $(c, e)$
• Weight 3: $(b, c)$
• Weight $x$: $(b, e)$

To construct a Minimum Weight Spanning Tree (MWST):

1. We must select the two minimum-weight edges of weight 1: $(a, e)$ and $(d, e)$. This connects vertices $a, d, e$ into a single component of weight $1 + 1 = 2$.
2. We now need to connect the remaining vertices $b$ and $c$ to this component at the minimum possible cost.

To maximize the number of MWSTs, we choose $x = 2$ for the edge $(b, e)$:

• Connecting $b$: We have two options of weight 2, which are $(a, b)$ and $(b, e)$.
• Connecting $c$: We have two options of weight 2, which are $(c, d)$ and $(c, e)$.

Since these choices are independent and do not form any cycles, the total number of MWSTs is:

$$\text{Number of MWSTs} = 2 \times 2 = 4$$