Here's one from the problem set in Basic Techniques of Combinatorial Theory by Daniel I.A. Cohen (1978).
Let n be the number of people who shook hands an odd number of times at a party last night. Prove that n is even.
The technique I used to prove this is to start with the basic case of 1 handshake. If 1 handshake has occurred then 2 people shook hands an odd number of times (1) (n = 2). From there, look at the possibilities of extending this network of handshakes [you can also represent it as a graph of points (people) connected by line or curve segments (handshakes)*]. There are 3 possibilities for extension:
1. An odd person (a person who shook an odd number of hands) can shake hands with an even.
The parities switch (odd becomes even, even becomes odd), and n stays the same.
2. An odd can shake hands with another odd.
Both become evens, the n decreases by two.
3. An even can shake hands with another even.
Both become odds, the n increases by two.
Since any "handshake graph" can start by connecting 2 people by 1 handshake (2 odds), and the number of odd people can only (1) stay the same, (2) decrease by 2, or (3) increase by 2, it follows that the n will always be even.
*More generally, this also proves that in such a graph, the number of nodes connected by an odd number of lines is always even. This also holds for graphs where nodes connect to each other more than once (such a multi-graph would represent people shaking hands with each other more than once).
