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 \setminus S$ reacts with an odd number of compounds. II. At least one compound in $U \setminus S$ reacts with an odd number of compounds. III. Each compound in $U \setminus S$ reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE?

Let the reaction relationships between compounds be represented as an undirected graph $G = (V, E)$, where:

• The vertex set $V = U$ has $|V| = 23$.

• An edge exists between two vertices if the corresponding compounds react with each other.

According to the Handshaking Lemma in graph theory:

This implies that the sum of degrees of all vertices in any undirected graph is always even. Consequently, the number of vertices with an odd degree must be even.

We are given:

• A subset $S \subset U$ with $|S| = 9$.

• For every vertex $v \in S$, $\deg(v) = 3$ (which is odd).

Since $|S| = 9$, there are currently 9 vertices with an odd degree in $S$. For the total count of odd-degree vertices in the graph to be an even number, the remaining set $U \setminus S$ must contain an odd number of odd-degree vertices (which is at least 1).

Therefore, at least one compound in $U \setminus S$ must react with an odd number of compounds, making Statement II ALWAYS TRUE.