GATE CS 2024 Set 2 — Question 51

Let $w(e)$ denote the weight of edge $e$. The weight of a spanning tree $T$ is $W(T) = \sum_{e \in T} w(e)$. We are given that W(T) is even for every spanning tree $T$ of $G$.Consider any cycle $C$ in $G$. Let $e$ be an edge in $C$. Since $G$ is connected, there exists a spanning tree $T$ such that $T$ contains all edges of $C$ except $e$ (i.e., $e$ is the fundamental cycle edge with respect to $T$).
Let $f$ be any other edge in $C$. Since $f \in T$ and $f$ is on the unique cycle formed by adding $e$ to $T$, the set of edges $T' = (T \setminus \{f\}) \cup \{e\}$ forms another spanning tree of $G$.The weights of $T$ and $T'$ are:
$W(T) = W_{common} + w(f)$
$W(T') = W_{common} + w(e)$We are given that both W(T) and $W(T')$ are even. Therefore, their difference must be even:
$W(T') - W(T) = w(e) - w(f) \equiv 0 \pmod 2$
$\implies w(e) \equiv w(f) \pmod 2$This implies that any two edges $e$ and $f$ in the cycle $C$ must have the same parity (both even or both odd). Since this holds for any pair of edges in $C$, all edges in the cycle $C$ must have the same parity.Thus, for every cycle $C$, either all edges in $C$ are even, or all edges in $C$ are odd. This corresponds to statement (D).Counter-examples for other options:

• (A) & (C): Consider a graph consisting of a single cycle of length 3 (triangle) with edge weights 1, 1, 1. The spanning trees have weights $1+1=2$ (even). This satisfies the condition. However, the edges are odd, so (A) and (C) are false.
• (B): Consider two disjoint triangles, one with weights (1, 1, 1) and another with weights (2, 2, 2), connected by a path of two edges with weights 1, 1. The total weight of any spanning tree will be sum of (2 edges from triangle 1) + (2 edges from triangle 2) + (path edges). Sum = (odd+odd) + (even+even) + (odd+odd) = even + even + even = even. This graph satisfies the condition. However, it contains both odd and even edges, so (B) is false.