Here's one from the problem set in

**Basic Techniques of Combinatorial Theory**by

*Daniel I.A. Cohen*(1978).

*n*

**L**et*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).