1. ## Handshaking Lemma

Handshaking Lemma. At a convention, the number of delegates who shake hands an odd number of times is even.

Proof. Let $\displaystyle D_{1}, \ldots , D_n$ be the delegates. Apply double counting to the set of ordered pairs $\displaystyle (D_i, D_j)$ for which $\displaystyle D_i$ and $\displaystyle D_j$ shake hands with each other at the convention. Let $\displaystyle x_i$ be the number of times that $\displaystyle D_i$ shakes hands, and $\displaystyle y$ the total number of handshakes that occur. The number of pairs is $\displaystyle \sum_{i=1}^{n} x_i$. However each handshake gives rise to two pairs $\displaystyle (D_i, D_j)$ and $\displaystyle (D_j, D_i)$. So $\displaystyle \sum_{i=1}^{n} x_i = 2y$. But how does this imply that the number of delegates that shakes hands an odd number of times is even? Because $\displaystyle n$ could be even and each $\displaystyle x_i$ could be even (e.g. $\displaystyle 2+4+6+8 = 20$).

2. In the general case we have the following: Let $\displaystyle A = \{a_{1}, \ldots, a_{m} \}$ and $\displaystyle B = \{b_1, \ldots, b_n \}$ be sets. Let $\displaystyle S$ be a subset of $\displaystyle A \times B$. Suppose that, for $\displaystyle i=1, \ldots m$, the element $\displaystyle a_i$ is the first component of $\displaystyle x_i$ pairs in $\displaystyle S$, while, for $\displaystyle j= 1, \ldots, n$, the element $\displaystyle b_j$ is the second component of $\displaystyle y_j$ pairs in $\displaystyle S$. Then $\displaystyle |S| = \sum_{i=1}^{m} x_i = \sum_{j=1}^{n} y_j$.

So suppose $\displaystyle A = \{1,3,4,5,6 \}$ and $\displaystyle B = \{7,9,2 \}$. So if $\displaystyle 1$ is the first component of $\displaystyle x_1$ pairs of $\displaystyle S$, $\displaystyle 3$ is the first component of $\displaystyle x_2$ pairs of $\displaystyle S$ etc.. and $\displaystyle 7$ is the second component of $\displaystyle y_1$ pairs of $\displaystyle S$ etc...then $\displaystyle \sum_{i=1}^{5} x_i = \sum_{j=1}^{3} y_j = |S|$.

But we don't know what $\displaystyle x_i$ and $\displaystyle y_j$ are. We just know that they represent the number of pairs with the first component being $\displaystyle a_i$ and the second component being $\displaystyle b_j$ respectively. Is this the whole point?

3. Isn't this the same as taking an unweighted, undirected graph and saying that:

The number of vertices with odd degree in a graph must be even?

If so, there is a pretty simple proof, unless you are trying to prove it using some other method besides graphs.

4. Originally Posted by Aryth
Isn't this the same as taking an unweighted, undirected graph and saying that:

The number of vertices with odd degree in a graph must be even?

If so, there is a pretty simple proof, unless you are trying to prove it using some other method besides graphs.

yes it is. But $\displaystyle 2+4+6+8 = 20$.

5. Ok, here's a proof of this theorem using the graphs:

Let $\displaystyle G = (V,E)$ be an unweighted, undirected graph.

Lets look at the sum of the degrees of its vertices (I'll call it M, though it is often referred to as K):

$\displaystyle M = \sum_{v\in V} deg_G (v)$

Applying the double-counting, each edge $\displaystyle e \in E$ will be counted twice, once for each each vertex to which it is incident.

As a result, the sum MUST be twice the number of edges of G.

$\displaystyle M = 2E$, which is even.

Now, all we do is take out the sum of all the degrees of vertices that are even to get the sum of all the odd degree vertices:

$\displaystyle \sum_{v \in V} deg_G (v) - \sum_{v \in V: deg_G (v) = 2m} deg_G (v) = \sum_{v \in V: deg_G (v) = 2m + 1} deg_G (v)$

This result on the right hand side must still be even, since it is the difference of two even numbers.
Because the sum is of exclusively odd terms, then there must be an even number of them for the sum on the right side to be even, thus the desired result is achieved.

6. Originally Posted by Aryth
Ok, here's a proof of this theorem using the graphs:

Let $\displaystyle G = (V,E)$ be an unweighted, undirected graph.

Lets look at the sum of the degrees of its vertices (I'll call it M, though it is often referred to as K):

$\displaystyle M = \sum_{v\in V} deg_G (v)$

Applying the double-counting, each edge $\displaystyle e \in E$ will be counted twice, once for each each vertex to which it is incident.

As a result, the sum MUST be twice the number of edges of G.

$\displaystyle M = 2E$, which is even.

Now, all we do is take out the sum of all the degrees of vertices that are even to get the sum of all the odd degree vertices:

$\displaystyle \sum_{v \in V} deg_G (v) - \sum_{v \in V: deg_G (v) = 2m} deg_G (v) = \sum_{v \in V: deg_G (v) = 2m + 1} deg_G (v)$

This result on the right hand side must still be even, since it is the difference of two even numbers.
Because the sum is of exclusively odd terms, then there must be an even number of them for the sum on the right side to be even, thus the desired result is achieved.
I see...so in my case we don't even consider things like $\displaystyle 2+4+6+8$.

7. Well, what you're saying is true, but the the handshaking lemma specifically talks about vertices with an ODD degree. With a sum like 2 + 4 + 6 + 8, you're dealing with all even degrees, which is going to be even anyway.