GATE CS 2016 Set 2 Q.38 (CS Q.28): Graph Theory

Consider a set $U$ of 23 different compounds in a Chemistry lab. There is a subset $S$ of $U$ of 9 compounds, each of which reacts with exactly 3 compounds of $U$ . Consider the following statements:

I. Each compound in $U \setminus S$ reacts with an odd number of compounds.
II. At least one compound in $U \setminus S$ reacts with an odd number of compounds.
III. Each compound in $U \setminus S$ reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

Only I

Only II

Only III

None

Official answer and solution

Official answer: B
From: Official GATE 2016 answer key

Solution

Model compound reactions as an undirected graph and use the Handshaking Lemma to deduce degree parity.

Model the 23 compounds as an undirected graph $G = (V, E)$ , where each vertex represents a compound and an edge exists between two vertices if the corresponding compounds react with each other. Thus, $|V| = 23$ .

By the Handshaking Lemma, the sum of degrees of all vertices in an undirected graph equals twice the number of edges, which is always an even integer:

\sum_{v \in V} \deg(v) = 2|E| = \text{Even}

We are given a subset $S \subset U$ of 9 compounds, each reacting with exactly 3 compounds. Hence, for each $v \in S$ , $\deg(v) = 3$ .

The sum of degrees in $S$ is:

\sum_{v \in S} \deg(v) = 9 \times 3 = 27 \quad (\text{an ODD number})

Split the total degree sum across $S$ and $U \setminus S$ :

\sum_{v \in S} \deg(v) + \sum_{u \in U \setminus S} \deg(u) = \text{Even}

\text{Odd} + \sum_{u \in U \setminus S} \deg(u) = \text{Even} \implies \sum_{u \in U \setminus S} \deg(u) \text{ must be ODD}

A sum of integers can be odd if and only if there is an odd number of odd terms in the summation. In particular, the number of compounds in $U \setminus S$ with an odd degree cannot be zero; there must be at least one compound in $U \setminus S$ with an odd degree.

Therefore, Statement II ("At least one compound in $U \setminus S$ reacts with an odd number of compounds") is ALWAYS TRUE.

Final answer

Common trap

Concluding that all remaining compounds must have odd degrees (only the count of odd-degree vertices must be odd, not all of them).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 38 of 65, printed as CS Q.28
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source