GATE 2024 CS2 Q.51: solution and answer

Official answer: DSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

1. Reduce the problem to edge-weight parities: let $x_e=w(e)\mathrm{mod}2$; the hypothesis is that every spanning tree's weight is even, i.e., ${\sum }_{e\in T}{x}_e\equiv 0(\mathrm{mod}2)$ for every spanning tree $T$.

2. Take any simple cycle $C$ in $G$ and any edge $e_k\in C$. Removing $e_k$ from $C$ leaves a path (a forest), which can always be extended, in a connected graph, to a full spanning tree $T$ of $G$ that does not contain $e_k$ (adding $e_k$ back would close a cycle). Since $T$ is a tree, the unique path between $e_k$'s endpoints inside $T$ must be exactly this path $C-e_k$ — so $C$ is precisely the fundamental cycle of $e_k$ with respect to $T$.

3. For every other edge $e_i$ of $C$ (so $e_i\in T$, lying on that tree path), the standard spanning-tree exchange property gives another spanning tree $T^{\prime }=T-e_i+e_k$.

4. Compare weights: $\text{weight}(T^{\prime })=\text{weight}(T)-w(e_i)+w(e_k)$. Since both $T$ and $T^{\prime }$ have even weight by hypothesis, subtracting mod 2 forces $w(e_i)\equiv w(e_k)(\mathrm{mod}2)$.

5. Since $e_k$ was an arbitrary edge of $C$, this parity-matching holds between every pair of edges of $C$: all edges of any cycle $C$ in $G$ share the same parity (all even, or all odd). This is exactly statement (D), proved true for every graph $G$ satisfying the hypothesis.

6. Kill (A) and (C): take a triangle with all three edges of weight $1$. Every spanning tree is any $2$ of the $3$ edges, weight $1+1=2$ (even) — hypothesis holds. But the edges are all odd, not all even (kills A), and the triangle (the only cycle) does not have all-even edges (kills C). Note this example does not yet refute (B), since all edges here are uniformly odd, which satisfies B's second disjunct.

7. Kill (B): take two triangles sharing exactly one vertex — one with all edges of weight $2$ (even), the other with all edges of weight $1$ (odd). Any spanning tree must use $2$ edges from each triangle (total $4$ edges for the $5$ vertices), and any such choice gives weight $(2+2)+(1+1)=6$, always even — hypothesis holds. But the edges of $G$ are neither uniformly even (the odd triangle breaks this) nor uniformly odd (the even triangle breaks this), so (B) is false here.

8. Since (A), (B), (C) each admit a counterexample while (D) was proved to hold for every valid $G$, the only statement guaranteed TRUE for every such $G$ is (D).