Handshake Lemma

Problem: Prove or disprove: at a party of n people, there must be an even number of people who have an odd number of friends at the party.

Solution: Let P be the set of all people, and for any person p \in P, let d(p) be the number of friends that person has. Let f be the total number of friendships between pairs of people at the party. Since each friendship among two friends at the party concerns exactly two people, we see that the following is true:

\displaystyle \sum_{p \in P} d(p) = 2f

In other words, counting up all of the number of friends that each person has will always be twice the number of total friendships. In particular, this number is always even. If there were an odd number of people with an odd number of friends at the party, and everyone else had an even number of friends, then the total number \sum_{p \in P} d(p) would necessarily be odd.

Hence, there can only be an even number of people with an odd number of friends at the party. \square

Discussion: This is a proof by “double-counting,” so to speak. Double counting proves an identity by showing that each side of the equality can be thought of as a different way of counting elements in the same set. In the above proof, we are counting the set of one-sided friendships in two different ways.

This technique comes up all over mathematics (particularly in combinatorics, the field of maths concerned with counting things). We can relate this to graph theory (see our very basic introduction to the topic), by seeing that a party is just a graph where the vertices are people and the edges are friendships. This theorem then says that for any graph, the sum of the degrees of each vertex is twice the number of edges, and hence always even.

Double counting has been used to prove a number of identities, and it can even be used to prove something as interesting as Fermat’s Little Theorem (which has quite a few proofs, and quite a few uses!) and counting the number of trees made from a set of n distinct vertices (it’s quite large: O(n^n) in fact!).

Advertisements

3 thoughts on “Handshake Lemma

  1. “If there were an odd number of people with an odd number of friends at the party, and everyone else had an even number of friends”
    ..
    Who is everyone else here .. ?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s