The GATE Grind

GATE 2024 CS (CS2) – Question 51

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple select

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

  1. All edges in $G$ have even weight
  2. All edges in $G$ have even weight OR all edges in $G$ have odd weight
  3. In each cycle $C$ in $G$, all edges in $C$ have even weight
  4. In each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight

Practise this question in The GATE Grind →

Show answer and explanation

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.