Project ForgeConsider 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 \ S reacts with an odd number of compounds. II. At least one compound in U \ S reacts with an odd number of compounds. III. Each compound in U \ S reacts with an even number of compounds.
Which one of the above statements is ALWAYS TRUE?
- AOnly I
- Only II
- COnly III
- DNone
Explanation
Model compounds as vertices and 'reacts with' as an edge — this is a graph on 23 vertices. The 9 vertices in S each have degree exactly 3, so their degree-sum is 9×3=27 (odd). By the Handshaking Lemma, the TOTAL degree-sum over ALL 23 vertices must be even (it equals twice the edge count). So the degree-sum over the remaining 14 vertices (U\S) must have parity even−odd = odd. A sum of 14 integers is odd only if an odd number of them (hence at least one) are themselves odd. So at least one compound in U\S must react with an odd number of compounds — statement II is always true. (Statements I and III both claim uniform parity across all of U\S, which isn't forced — only that at least one is odd.)
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.