GATE CS 2016 Set 1 Q40 — Minimum Spanning Trees

We analyze the two statements for an undirected simple graph $G$ with distinct edge weights:

Statement I is FALSE:

Consider a graph with vertices $A, B, C, D$ and the following edges and weights:

• $(A, B) = 1$
• $(B, C) = 2$
• $(A, C) = 3$
• $(C, D) = 4$
• $(A, D) = 5$

Consider the cycle $A-C-D-A$ with edge weights $3, 4, 5$. The lightest edge of this cycle is $e = (A, C)$ with weight $3$.

Using Kruskal's algorithm, the unique MST consists of edges $(A, B)$, $(B, C)$, and $(C, D)$ with total weight $1 + 2 + 4 = 7$. This MST does not include $e = (A, C)$. Thus, Statement I does not hold.

Statement II is TRUE:

This is the standard Cycle Property of Minimum Spanning Trees. It states that for any cycle in a graph with distinct edge weights, the heaviest edge of that cycle can never belong to any MST. If we were to include this heaviest edge $e$ in an MST, removing it and adding any other lighter edge from the cycle would yield a spanning tree of strictly smaller weight, contradicting the minimality of the MST.

Therefore, only Statement II is TRUE.