Handshaking Lemma. At a convention, the number of delegates who shake hands an odd number of times is even.
Proof. Let be the delegates. Apply double counting to the set of ordered pairs for which and shake hands with each other at the convention. Let be the number of times that shakes hands, and the total number of handshakes that occur. The number of pairs is . However each handshake gives rise to two pairs and . So . But how does this imply that the number of delegates that shakes hands an odd number of times is even? Because could be even and each could be even (e.g. ).