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$?

Question

cdquestions Admin · Accepted Answer

If every spanning tree in $G$ has an even weight, it implies a specific structure for the graph $G$. Consider the properties: Option (A): Incorrect. Not all edges in $G$ need to have even weight; some edges can have odd weights as long as the total weight of spanning trees remains even. Option (B): Incorrect. $G$ may contain both even and odd weighted edges. Option (C): Incorrect. It is not necessary for all edges in any cycle $C$ to have even weight. Option (D): Correct. For every cycle $C$ in $G$, the parity of the edges must be consistent (all even or all odd) to ensure that every spanning tree has an even total weight. Final Answer: $$ \boxed{\text{(D)}} $$

Answer

All edges in $G$ have even weight

Answer

All edges in $G$ have even weight OR} all edges in $G$ have odd weight

Answer

In each cycle $C$ in $G$, all edges in $C$ have even weight

Answer

In each cycle $C$ in $G$, either all edges in $C$ have even weight OR} all edges in $C$ have odd weight

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\)?

Show Hint

The Correct Option is D

Solution and Explanation

Top Questions on Miscellaneous

Questions Asked in GATE CS exam