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\) ?
Answer
(D)
Explanation
(D) holds. Suppose a cycle \(C\) has an even edge \(e\) and an odd edge \(f\). Extend the path \(C - f\) to a spanning tree \(T\); it contains \(e\) but not \(f\). Removing \(e\) splits \(T\) into two parts, and \(f\) must join them, because the rest of the cycle links the ends of \(e\). So \(T - e + f\) is another spanning tree whose weight differs from that of \(T\) by an odd amount, and both cannot be even.
The others fail. A triangle with weights 1, 1, 1 has every spanning tree of weight 2, yet its edges are odd, which rules out (A) and (C). A path with weights 1, 1, 2 is its own only spanning tree (weight 4) and mixes parities, which rules out (B).
Answer: D