Question 51

Let $C$ be any cycle in $G$, and let $e, e'$ be any two edges in $C$. Extend $C \setminus \{e\}$ to a spanning tree $T$ of $G$ (since $C \setminus \{e\}$ is acyclic, it can always be extended to a spanning tree $T$ that does not contain $e$).

Now replace $e' \in C$ with $e$ to form a new spanning tree $T' = (T \setminus \{e'\}) \cup \{e\}$. The weights of $T$ and $T'$ satisfy:

Since every spanning tree in $G$ has even weight, $w(T') - w(T)$ is even, which implies $w(e) \equiv w(e') \pmod 2$. Because this holds for every pair of edges $e, e'$ in $C$, all edges in $C$ have the same parity (either all even or all odd). Thus (D) is TRUE.

Why (A), (B), and (C) are FALSE:

• Consider a triangle $C_3$ in which all $3$ edges have odd weight $1$: every spanning tree has $2$ edges of weight $1$ (total weight $2$, which is even), falsifying (A) and (C).
• Attach a bridge of even weight $2$ to that triangle: now every spanning tree has weight $1 + 1 + 2 = 4$ (even), yet $G$ has both odd-weight and even-weight edges, falsifying (B).