GATE CS 2021 Set 2 Q1 — Minimum Spanning Trees

We analyze the two statements individually:

Statement $S_1$: False

Consider a counterexample where $G$ is a cycle graph $C_3$ with three vertices $u, v, w$ and three edges of equal minimum weight:

• $e_1 = (u, v)$ with weight $1$
• $e_2 = (v, w)$ with weight $1$
• $e_3 = (w, u)$ with weight $1$

The minimum edge weight in $G$ is $1$. Any Minimum Spanning Tree (MST) of this graph must contain exactly $2$ edges to avoid a cycle. The possible MSTs are:

• $T_1 = \{e_1, e_2\}$
• $T_2 = \{e_2, e_3\}$
• $T_3 = \{e_3, e_1\}$

The intersection of all these MSTs is empty ($T_1 \cap T_2 \cap T_3 = \emptyset$). Thus, there is no single minimum weight edge that is present in every MST of $G$.

Statement $S_2$: True

This is a standard theorem in graph theory. If all edge weights in a connected undirected graph $G$ are distinct, then $G$ has a unique minimum spanning tree.

Proof sketch: Suppose there are two distinct MSTs, $T_1$ and $T_2$. Let $e$ be the edge of minimum weight that belongs to one tree but not the other (say, $e \in T_1 \setminus T_2$). Adding $e$ to $T_2$ creates a unique cycle $C$. This cycle must contain at least one edge $e'$ that is not in $T_1$. Since all edge weights are distinct, and $e$ is the minimum weight edge in the symmetric difference, we must have $\text{weight}(e) < \text{weight}(e')$. Replacing $e'$ with $e$ in $T_2$ yields a spanning tree with a strictly smaller weight than $T_2$, which contradicts the assumption that $T_2$ is an MST. Thus, the MST must be unique.

Hence, $S_1$ is false and $S_2$ is true.