JAMIA 2022 — Mathematics PYQ

1. Modeling the Problem

Imagine each person on Earth is a vertex (point) in a graph, and each handshake between two people is an edge (line) connecting them.

• Let $V$ be the set of all people (vertices).

• Let $E$ be the set of all handshakes (edges).

• Let $d(v)$ be the degree of a vertex $v$, which represents the number of handshakes that person $v$ has made.

2. The Handshaking Lemma

In any graph, the sum of the degrees of all vertices is exactly twice the number of edges. This is because every single handshake (edge) involves exactly two people (vertices), contributing "1" to the count of each person.

Since $2|E|$ is always an even number, the sum of all handshakes made by every person on Earth must be even.

3. Splitting the Sum

We can split the total sum of degrees into two groups:

1. People who have shaken hands an even number of times ($V_{even}$).

2. People who have shaken hands an odd number of times ($V_{odd}$).

4. Logical Deduction

• The sum of even numbers (${\sum }_{v\in V_{even}}d(v)$) is always even.

• For the total sum to remain even, the sum of the odd degrees (${\sum }_{v\in V_{odd}}d(v)$) must also be even.

For a sum of odd numbers to result in an even total, there must be an even number of terms in that sum.

Final Answer

The number of people who have shaken hands an odd number of times is always even.