GATE CS 2024 Set 2 Q41 — Graphs: Connectivity, Matching, Colouring

Let $T$ be any spanning tree of $G$. By the given condition, its weight $w(T)$ must be even.

For any cycle $C$ in $G$, we can find a spanning tree $T$ that contains all edges of $C$ except for one edge $e \in C$. For any other edge $e' \in C$ (where $e' \neq e$), the subgraph $T' = T \cup \{e\} \setminus \{e'\}$ is also a spanning tree of $G$, meaning its weight $w(T')$ must also be even.

The relationship between the weights of these two spanning trees is: $$w(T') = w(T) + w(e) - w(e')$$ Since both $w(T)$ and $w(T')$ are even, their difference must also be even: $$w(e) - w(e') \equiv 0 \pmod 2 \implies w(e) \equiv w(e') \pmod 2$$ Since this holds for any choice of $e' \in C$, all edges in the cycle $C$ must have the same parity. Thus, either all edges in $C$ have even weight, or all edges in $C$ have odd weight. This makes Option D correct.

Counterexamples for other options:

• A & B: Let $G$ be a tree with edge weights $2, 1, 1$. The only spanning tree is $G$ itself with an even weight of $4$. Here, some edges are odd and some are even, disproving both A and B.
• C: Let $G$ be a cycle of length 3 with edge weights $1, 1, 1$. Every spanning tree has weight $2$ (even), but the cycle contains odd-weighted edges, disproving C.