Skip to content
GATEiit

GATE CSE 2024 Session 2 Q51: Edge weights when every spanning tree has even weight

Question

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

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: D (official GATE 2024 final answer key)

Concept used: Exchanging one edge of a cycle for another gives a new spanning tree, so edges on a common cycle share parity.

First step: A path with two edges of weight 1 is its own only spanning tree (weight 2), which refutes (A); for (D), swap a cycle edge with another edge of the same cycle and compare the two trees' weights.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2024 Session 2 questions →