1 Proof: Handshake Parity

I'm going to try posting on math from time to time.  I'm doing this for my own enjoyment: sometimes I might try to do posts that require a little more research, or require some preliminary explanations, but generally I'll just post my solutions to various problems I've come across (usually in books), and try to explain them as clearly as I can.  I'm sure I'm not the first to come up with any of these solutions, but any mistakes here are my own.

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).