TITLE: Practical example of graph theory?
QUESTION [0 upvotes]: Consider a set $U$ of $23$ different compounds in a chemistry lab. There is a subset $S$ of $U$ having $9$ compounds, each of which
reacts with exactly $3$ compounds of $U$. Suppose $U-S$ is the set of elements of $U$ which are not in $S$.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?

REPLY [0 votes]: Denoting the compounds by $23$ vertices and an edge (undirected) is used to represent the reacting ability of a pair of compounds. Using Handshaking theorem, $\sum_{i=1}^{23} deg(v_i)=2|E|$, where $|E|$ is the number of edges in the graph.
This gives $9×3 +\sum_{i=10}^{23}deg(v_i)=2|E|$
or $27+\sum_{i=10}^{23}deg(v_i)=2|E|$ ............$(a)$
Since RHS is an even number, so in order to satisfy $(a)$, atleast one vertex (or $3, 5, 7$..) from the remaining $14$ must be of  odd degree.
{"set_name": "stack_exchange", "score": 0, "question_id": 2458778}