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$?
All edges in $G$ have even weight
All edges in $G$ have even weight OR all edges in $G$ have odd weight
In each cycle $C$ in $G$, all edges in $C$ have even weight
In each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight
Correct answer: (D) In each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight
Explanation
Swapping one edge of a spanning tree for a cycle edge preserves even weight only if the two edges have equal parity, so all edges in a cycle share parity. Different cycles can differ (e.g., a bridge-connected structure), so A, B, C are not forced.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
GATE 2024 CS (CS2) Q60– The chromatic number of a graph is the minimum number of colours used in a proper…
GATE 2023 CS Q55– Let G be a simple, finite, undirected graph with vertex set \v 1,,v n\. Let (G) denote the…
GATE 2022 CS Q30– Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the…
GATE 2022 CS Q37– Consider a simple undirected unweighted graph with at least three vertices. If A is the…
GATE 2022 CS Q50– The following simple undirected graph is referred to as the Peterson graph. Which of the…
GATE 2022 CS Q52– Which of the properties hold for the adjacency matrix A of a simple undirected unweighted…