GATE CS 2016 Set 2 — Question 38

Let the compounds be vertices in a graph $G=(V, E)$ where an edge represents a reaction. Let $U$ be the set of vertices, so $|U| = 23$. Let $S \subset U$ with $|S| = 9$. We are given that for every vertex $v \in S$, the degree $d(v) = 3$.Let $U \setminus S$ be the set of the remaining vertices. The size of this set is $|U \setminus S| = 23 - 9 = 14$.By the Handshaking Lemma, the sum of degrees in a graph is equal to twice the number of edges, which is always an even number:$$\sum_{v \in U} d(v) = 2|E|$$Splitting the sum into vertices in $S$ and vertices in $U \setminus S$:$$\sum_{v \in S} d(v) + \sum_{v \in U \setminus S} d(v) = 2|E|$$Substitute the known values for $S$:$$\sum_{v \in S} d(v) = 9 \times 3 = 27$$So:$$27 + \sum_{v \in U \setminus S} d(v) = \text{Even Number}$$Since 27 is odd, for the sum to be even, the term $\sum_{v \in U \setminus S} d(v)$ must be odd (because Odd + Odd = Even).If the sum of a set of integers is odd, then at least one of the integers must be odd. It is not possible for all of them to be even (which makes Statement III false). It is not necessary for all of them to be odd (Statement I is not necessarily true; e.g., one could be odd and the rest even).Therefore, Statement II ("At least one compound in $U \setminus S$ reacts with an odd number of compounds") is always true.