Question 57

The graph has 5 vertices $\{V_1, V_2, V_3, V_4, V_5\}$ and 7 edges with weights: $(V_1, V_4)=1, (V_1, V_5)=3, (V_2, V_1)=4, (V_2, V_4)=4, (V_4, V_5)=4, (V_1, V_3)=x, (V_5, V_3)=5$.

Edges $(V_1, V_4)$ [weight 1] and $(V_1, V_5)$ [weight 3] have the smallest weights and must be included in every MWST, connecting component $\{V_1, V_4, V_5\}$. Edge $(V_4, V_5)$ of weight 4 creates a cycle with them and is never selected.

To connect $V_2$ to $\{V_1, V_4, V_5\}$, there are two edges of weight 4: $(V_2, V_1)$ and $(V_2, V_4)$. Choosing either edge connects $V_2$ at minimal cost, giving $\binom{2}{1} = 2$ independent choices.

To connect $V_3$, the available edges are $(V_1, V_3)$ of weight $x$ and $(V_5, V_3)$ of weight 5.

• If $x < 5$, $(V_1, V_3)$ is strictly smaller, giving only 1 choice for $V_3$.
• If $x > 5$, $(V_5, V_3)$ is strictly smaller, giving only 1 choice for $V_3$.
• If $x = 5$, both $(V_1, V_3)$ and $(V_5, V_3)$ have weight 5, giving $\binom{2}{1} = 2$ independent choices for $V_3$.

Thus, setting $x = 5$ maximizes the number of MWSTs to $2 \times 2 = 4$.