Graph Theory Tidbits

You are at a cocktail party. People are introducing themselves and shaking hands. Since parties make you uncomfortable, you lean against the wall. Rather than having meaningful human interaction, you can do a little graph theory instead, which is much more fun. With a little thinking, you can derive two interesting conclusions:

1. At least two people shook the same number of hands.
2. An even number of people shook an odd number of hands.

The first result rests on the wonderfully named "pigeonhole principle." Consider what it would take for no two people to shake the same number of hands: each person would have his or her own unique "shake-count". We consider each shake-count a "pigeonhole", because it's like a slot that we fill with a person. So Aziz shook zero hands, Bob shook one hand, Carmen two hands, etc. With n people, we could assign "shake-counts" from 0 all the way up to Zaphod who shook n-1 hands (assuming we don't permit someone to shake hands with himself). This is n different shake-counts, so it seems we could indeed have n people, each with their own shake-count. But consider what it implies for Aziz to have a shake-count of zero: outcast that he is, he didn't shake anyone's hand at all. Zaphod, with a shake-count of n-1, shook the hand of everyone at the party. But Aziz and Zaphod can't be at the same party: if Zaphod succeeds in shaking everyone's hand, then Aziz can't have shook no hands, and vice-versa. Hence any single party has only n-1 pigeonholes for shake-counts. When you try to stick n people in n-1 pigeonholes, you'll end up with at least two people in the same pigeonhole. So at least two people shook the same number of hands. Hoorah!

---

The second result is even more kooky sounding, but it also follows from very simple principles. Consider the total of each partygoer's personal "shake-count". Each handshake involves two people, so the sum of everyone's shake-counts must equal twice the total number of handshakes. (Think about that one for a sec to make sure you get it). This means that the sum of shake-counts is an even number. Now, consider the people who shook an even number of hands: the sum of their shake-counts must be an even number too, since when you add together even numbers you get even numbers. This means that the remaining sum of shake-counts, the sum of the shake-counts of people who shook an odd number of hands, must also be an even number. Now, to get an even number by adding up odd shake-counts, there must be an even number of such people. (Simple example: 3 + 3 = 6 (two people, even sum), but 3 + 3 + 3 = 9 (three people, odd sum). So, there is always an even number of people that have shaken an odd number of hands! Happy Graph Theory Awareness Week!