n people (n >= 2) attend a party, and each person shakes hands with some of the others.

logic/invariants/odd.handshakes New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

n people (n >= 2) attend a party, and each person shakes hands with
some of the others.  Prove that the number of people who have shaken an
odd number of hands is always even (zero counts as even).

Equivalently: in any graph, the number of vertices of odd degree is
even.

Show solution

Before any hands have been shaken, the number of people who have shaken
an odd number of hands is zero, which is even.  If two people who have
shaken an even number of hands shake, the number of odds has increased
by two.  If one odd and one even shake, there is no change.  If two
odds shake, the number of odds decrease by two.  All changes are even,
so the parity of the number of odds never changes.

-- Ross Millikan <millikan.ross@ssd.loral.com>

[ Editor: the problem was posted by Ng Sze Chiak
<szcng@merlion.singnet.com.sg>. ]

[ Editor: a shorter proof, rec.puzzles, June 1995. ]

Every handshake takes two people.
The number of shaken hands total is therefore even.
For any sum of numbers to be even, there must be an even amount of odd
numbers.

-- Enigma GB <enigmagb@aol.com>

Very concise and easy solution.  Well done :)

-- Jonathan S. Haas <positron@devel.trimarkint.com>