Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which of the following statements is/are TRUE for every such graph G?
A. All edges in G have even weight OR all edges in G have odd weight
B. All edges in G have even weight
C. All edges in G have odd weight
D. In each cycle C in G, either all edges in C have odd weight OR all edges in C have even weight
GATE 2024 · Discrete Mathematics · Graph Connectivity · medium
Answer: D. In each cycle C in G, either all edges in C have odd weight OR all edges in C have even weight.
Fundamental-cycle parity argument: Let T be any spanning tree with even weight w(T). For any non-tree edge f in G, T + f contains exactly one fundamental cycle C_f. Swapping tree edge e in C_f for f gives T' = T - e + f with w(T') = w(T) + w(f) - w(e). Since w(T') must also be even, w(f) - w(e) must be even, so w(e) and w(f) have the same parity. This holds for every pair of edges in every fundamental cycle.
Check options A, B, C via counterexample: Consider a graph with a triangle having two even-weight edges and one cycle-completing edge: if the triangle edges are 2, 4, and 2+4=6 (all even), every spanning tree has even weight, but option C (all odd) fails. Similarly a graph with mixed but cycle-consistent parities shows options A and B can fail. Only option D (each cycle has uniform parity) is always satisfied.