edited by
16,413 views
85 votes
85 votes

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:

  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?

  1. Only I
  2. Only II
  3. Only III
  4. None.
edited by

8 Answers

Best answer
128 votes
128 votes

Option $B$ should be the correct answer.

It is given that the number of compounds in $U = 23$ and the number of compounds in $S = 9$, so the number of compounds in $U \backslash S= 23 - 9 = 14$.


Considering each of these compounds as nodes of a graph $G$.So, vetex set of $G$ is $U$ and $S$ is a subset of vertices of $G$. 

The relation "$A$ reacts with $B$" is a symmetric relation, that is $A$ reacts with $B$ is same as $B$ reacts with $A$.

For example, consider the following reaction:

$\text{HCl + NaOH} \rightarrow \text{NaCl + H}_{2} \text{O}$

Here, we can say either $\text{HCl}$ reacts with $\text{ NaOH}$ to produce $\text{NaCl + H}_{2} \text{O}$ or we can say that $\text{ NaOH}$ reacts with $\text{HCl}$ to produce $\text{NaCl + H}_{2} \text{O}$, so both of these statements are equivalent. 

Since, the relation based on which we are going to draw the edges is symmetric, we can use an undirected edge $\left ( A, B \right )$  between any two compounds to represent the fact that $A$ reacts with $B$ as well as $B$ reacts with $A$.


Each compound in $S$ reacts with exactly $3$ compounds in $U$.

It means that the degree of every node(or compound) in $S$ is $3$.

So, sum of all the degree in $S =$ number of nodes in $S \times $ degree of each node $= 9 \times 3 = 27$.

Now in $U \backslash S$ we have $14$ nodes(or compounds), thus clearly $U \backslash S$ contains an even number of compounds.

Now if each compound in $U \backslash S$ reacts with an even number of compounds, the sum of degrees of all the node in $U \backslash S$ would be even, and consequently, the sum of degrees of all the nodes in our graph $G$ would be odd as the sum of degrees of all the nodes in $S$ is odd, and an odd number added with an even number produces an odd number.

But since in a graph, every edge corresponds to two degrees and the number of edges in a graph must be a (non-negative)integral value & not fractional value hence the sum of the degrees all the nodes of a graph must be even. (This is Handshaking Lemma).

So, statement III should be false(always).


Also, adding fourteen odd numbers gives an even number.

Hence, if each compound in $U \backslash S$ reacts with an odd number of compounds, the sum of degrees of all the node in $U \backslash S$ would be even, and consequently, the sum of degrees of all the nodes in our graph $G$ would be odd as the sum of degrees of all the nodes in $S$ is odd, and an odd number added with an even number produces an odd number.

Again by using Handshaking Lemma, this is not possible.

So, statement I should also be false(always).


Thus, from the previous two cases, it can be observed that to satisfy the Handshaking Lemma for $G$, the sum of the degrees of all the nodes $U \backslash S$ must be odd.To make this happen, we must assign at least one node of $U \backslash S$, an odd degree.

If at least, one node(or compound) in $U \backslash S$ would have an odd degree( or reacts with odd numbers of compounds) then we can assign degrees in such a way that the sum of the degrees of all the nodes $U \backslash S$ will be odd, & thus the Handshaking Lemma would be satisfied.

Hence, statement II is the only statement which is guaranteed to be true always.


Moreover, we can also make some stronger claims from the given information like,

always an odd number of compounds in $U \backslash S$ reacts with an odd number of compounds and

at least, one compound in $S$ reacts with a compound in $U \backslash S$ and so on.

57 votes
57 votes

The sum of the degrees of all the vertices in a graph is equal to twice the number of edges.

Here, Set S has 9 elements and each element has a degree of 3 as each element in S  reacts to exactly 3 elements. So 9*3 + Sum. of degrees of vertices in U-S = 2* e

Since 2*e is even no, Sum of degrees of vertices in U-S is  odd .

Thus,some vertex in U-S must have odd degree. .At least one compound in U-S reacts with an odd number of compounds.

Option B is the correct answer.

edited by
12 votes
12 votes
In a  undirected graph there is always even no of vertices of odd degree it's a theorem so if 9 vertices are of odd degree in 3 implies there should be at least one vertice more of odd degree

So

2 is correct
2 votes
2 votes

There are set of ‘23’ different compounds.
U = 23
∃S ∋ (S⊂U)
Each component in ‘S’ reacts with exactly ‘3’ compounds of U,

If a component ‘a’ reacts with ‘b’, then it is obvious that ‘b’ also reacts with ‘a’.
It’s a kind of symmetric relation.>br> If we connect the react able compounds, it will be an undirected graph.
The sum of degree of vertices = 9 × 3 = 27
But, in the graph of ‘23’ vertices the sum of degree of vertices should be even because
 (di = degree of vertex i.e., = no. of edges)
But ‘27’ is not an even number.
To make it an even, one odd number should be added.
So, there exists atleast one compound in U/S reacts with an odd number of compounds.

Answer:

Related questions