• recategorized ago by
30,483 views
125 125 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.

12 Answers

Best answer
160 160 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.

• edited by
86 86 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
17 17 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
4 4 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.

3 3 votes

Let the set U of 23 compounds be modeled as an undirected graph whose vertices are $\{ a, b, \dots, n, 1, 2, \dots, 9 \}$

Let S⊂U be the subset consisting of the 9 vertices $\{1,2,…,9\}$

Each compound (node) of Set $S$ reacts to 3 compounds from $U$, so create three edges from all compounds (nodes) of S to that of U.

U \ S in our graph are nodes $\{a,b,…,n\}$


$I.$ Each compound in U \ S reacts with an odd number of compounds.

$False$ - because $Deg$($i$) = $2$ $i.e.$ $even$


$II.$ At least one compound in U \ S reacts with an odd number of compounds.

$True$ - because $Deg$($b$) = $3$ $i.e.$ $odd$


$III.$ Each compound in U \ S reacts with an even number of compounds

$False$ - because $Deg$($c$) = $3$ $i.e.$ $odd$

Hence, Answer - $B$

2 2 votes

We shall use graph theory to answer this question. Let $G$ be an undirected graph. Assume a vertex for each compound. Also there is an edge between two vertices if and only if the two compounds react. As an example case suppose that all the elements in $S$ react with only elements in $S$. So in the induced subgraph corresponding the vertices in $S$, each vertex has odd degree and there are $9$ vertices in $S$. So we have odd no. of vertices of odd degree which is not possible. So the tightest example which we can have is as shown:

If the situation is as given and let us assume that the vertices in $U\backslash S$ which are not shown ($11$ such vertices are there) do not react with anything, then we reach at contradiction of :

Statement 1 : Because, here in the above example the $11 (=  23-9\text{(vertices of S)}-3\text{(vertices in blue)}$ vertices have even degree. So every vertices does not have odd degree.

Statement 3: Because, here in the above example, the $3$ blue vertices have odd degree [$1$ as shown]. So every vertex does not have even degree.

What about statement 2? In this example statement 2 is correct. Why? Let us assume that statement 2 is false. So all the $14$ vertices of $U\backslash S$ should have even degrees in graph $G$. But in $G-S$ the three blue vertices should have odd degrees, which is not possible, as a graph should have an even no of vertices with odd degrees.

But we cannot say about the correctness of a statement, just by proving it correct for one example case. We need to show that it is true for all cases. So again let us assume that statement 2 is false. So all the $14$ vertices of $U\backslash S$ should have even degrees in graph $G$. So their degree sum is also even. Also the $9$ vertices in $S$ have degree $3$ each. So sum their degree sum is $9* 3=27$ which is odd. So sum of degrees of the vertices of the graph = even+odd= an odd number. But degree sum of the vertices of a graph graph is twice the number of edges in the graph and hence even. So we arrive at a contradiction and statement 2 is true indeed. [This proof actually also proves that statement 3 is false].


A formal proof that statement 1 is wrong: if all $14$ vertices in $U\backslash S$ have odd degree then their degree sum shall be odd. Also we know degree sum of the vertices in $S$ is odd, so the degree sum of the vertices in $G$ shall be odd which is not possible,

Answer:
Position:
Show:

Related questions

74 74 votes
10 answers 10 answers
24.4k
24.4k views
Akash Kanase asked Feb 12, 2016
24,438 views
A binary relation $R$ on $\mathbb{N} \times \mathbb{N}$ is defined as follows: $(a, b) R(c, d)$ if $a \leq c$ or $b \leq d$. Consider the following propositions:$P:$ $R$ ...
60 60 votes
6 answers 6 answers
26.3k
26.3k views
Akash Kanase asked Feb 12, 2016
26,349 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.