Skip to content
GATETECH
Official PYQ · 2016Set 2 · Q28Sets, Relations and FunctionsMCQ1 mark

GATE CS 2016 Set 2 Q28 — Sets, Relations and Functions

Explain with AI

Consider a set UU of 2323 different compounds in a chemistry lab. There is a subset SS of UU of 99 compounds, each of which reacts with exactly 33 compounds of UU. Consider the following statements:

  1. Each compound in U \ S reacts with an odd number of compounds.
  2. At least one compound in U \ S reacts with an odd number of compounds.
  3. Each compound in U \ S reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

Choose one option
View worked solution

Answer: B

We can model the compounds and their reactions as an undirected graph G=(V,E)G = (V, E), where the vertices V=UV = U represent the compounds and the edges represent the reactions between them.

By the Handshaking Lemma, the sum of the degrees of all vertices in any graph must be even:

∑v∈Vd(v)=2∣E∣\sum_{v ∈ V} d(v) = 2|E|

We can split this sum into the vertices in SS and the vertices in U∖SU \setminus S:

∑v∈Sd(v)+ule0pt15pt∑v∈U∖Sd(v)=2∣E∣\sum_{v ∈ S} d(v) + ule{0pt}{15pt}\sum_{v ∈ U \setminus S} d(v) = 2|E|

We are given that ∣S∣=9|S| = 9 and each compound in SS reacts with exactly 33 compounds, so d(v)=3d(v) = 3 for all v∈Sv ∈ S. This gives:

27+∑v∈U∖Sd(v)=2∣E∣27 + \sum_{v ∈ U \setminus S} d(v) = 2|E|

Since 2∣E∣2|E| is always even, the sum of the degrees of the vertices in U∖SU \setminus S must be odd:

∑v∈U∖Sd(v)=2∣E∣−27=odd\sum_{v ∈ U \setminus S} d(v) = 2|E| - 27 = \text{odd}

For a sum of integers to be odd, there must be at least one odd integer in the sum. Thus, at least one compound in U∖SU \setminus S must have an odd degree (i.e., react with an odd number of compounds). This makes Statement II always true, while Statements I and III are not necessarily true.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Sets, Relations and Functions questions