Consider a set U of 23 distinct compounds in a chemistry laboratory. Let S be…

Concept

In an undirected graph, the handshaking lemma says that the sum of all vertex degrees is twice the number of edges, so it is even. A sum of integers is odd exactly when an odd number of its terms are odd. Therefore, an odd degree sum over a vertex set means that an odd number of its vertices have odd degree.

Application

1. Model each compound as a vertex and each reaction as an undirected edge.

2. The 9 vertices in S each have degree 3, so their degree sum is 9 × 3 = 27, which is odd.

3. The degree sum of the entire graph is even. Hence the degree sum over U minus S is even minus 27, which is odd.

4. Thus an odd number of vertices in U minus S have odd degree: it may be 1, 3, 5, and so on, but it cannot be 0, 2, 4, and so on. In particular, at least one such vertex has odd degree.

Cross-check and contrast

If zero or any even number of vertices outside S—such as four—had odd degree, their total degree sum would be even. That contradicts the odd degree sum just obtained.

• “Only I” is not guaranteed because the odd number of odd-degree vertices need not equal all 14 vertices outside S.

• “Only III” would make the number of odd-degree vertices zero and their degree sum even.

• “None” overlooks the guaranteed existence established by the parity argument.

Therefore, the always-true statement is: at least one compound in U minus S reacts with an odd number of compounds (“Only II”).