Prove that if people in a room shake hands with whoever they know, the number of people who shake hands with an odd number of people is even. You are given that there are at least two people who know each other.
Solution: Let N be the total number of handshakes – the sum of handshakes made by every person in the room. This number must be even because every handshake is counted twice. Let n1 be the number of people who shook hands with an even number of people and n2 be the number of people who shook hands with an odd number of people. n1must be even. And we also argued that total number of handshakes = N must be even so N = 2M. But N = n1 + n2 = 2M. Since n1 is even, n2 must also be even.