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 S reacts with an odd number of compounds.
II. At least one compound in U S re

Question

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 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?

Accepted Answer

Only II. Model 'reacts with' as an undirected graph; the total degree sum is even. The 9 compounds in S contribute 9*3=27 (odd) to that sum, so the degrees of the other 14 compounds (U\S) must sum to an odd number, forcing at least one of them to have odd degree. Hence statement II is always true.

Solution

Related GATE Engineering Mathematics questions