Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose ev

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2024 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2024 question covers Minimum Spanning Trees (Kruskal and Prim) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2024 Algorithm question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose every spanning tree in G has even weight. Which of the following statements is/are TRUE for every such graph G?(A) All edges in G have even weight(B) All edges in G have even weight OR all edges in G have odd weight(C) In each cycle C in G, all edges in C have even weight(D) In each cycle C in G, either all edges in C have even weight OR all edges in C have odd weight

Accepted Answer

Correct Answer: (D) onlyConcept -- Spanning Trees and Graph Edge Weights: If every spanning tree of G has even weight, we need to determine which edge weight constraints follow.Key insight: Two spanning trees of a connected graph differ by a sequence of edge swaps. Swapping edge e (in T1 but not T2) with edge f (in T2 but not T1) changes the weight by (w(f) - w(e)). For both trees to have even weight, the difference must be even, so w(e) and w(f) must have the same parity (both even or both odd) whenever they are swap candidates in some spanning tree exchange.Any two edges that lie on a common cycle can be exchanged in some spanning tree swap. If in any cycle an edge with even weight and an edge with odd weight coexist, we can find two spanning trees differing in weight by an odd number, contradicting the hypothesis. Therefore in every cycle, all edges must have the same parity. This is precisely statement (D).Statements (A), (B), and (C) are too restrictive. A graph can have all-odd-weight spanning trees with some even and some odd edges (as long as parity is uniform within each cycle), showing A and C are not necessary. B allows only uniform parity globally, but D is weaker and more general, and D is the necessary and sufficient condition.

Master GATE-CS with Our Test Series

More Questions from Minimum Spanning Trees (Kruskal and Prim)

Frequently Asked Questions

Master GATE-CS with Our Test Series

More Questions from Minimum Spanning Trees (Kruskal and Prim)

Frequently Asked Questions