GATE CSE 2024 | Set 2 | Question: 41

Question

Let $\text{G}$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $\text{G}$ has even weight. Which of the following statements is/are TRUE for every such graph $\text{G}$?

• A. All edges in $\text{G}$ have even weight
• B. All edges in $\text{G}$ have even weight $\mathbf{O R}$ all edges in $\text{G}$ have odd weight
• C. In each cycle $\text{C}$ in $\text{G}$, all edges in $\text{C}$ have even weight
• D. In each cycle $\text{C}$ in $\text{G}$, either all edges in $\text{C}$ have even weight $\text{OR}$ all edges in $\text{C}$ have odd weight

Answer 1

Note that the given question is about Spanning Tree, Not about Minimum Spanning Tree.

Detailed Video Explanation: Spanning Tree Even Weight - GATE CSE 2024

Find counter-examples for option A,B,C in the above video solution.

Answer 2

I think the best approach would be to take counter examples for each case.

P.S. there may be better ways to solve this