1. ## Handshaking Lemma

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

Proof. Let $D_{1}, \ldots , D_n$ be the delegates. Apply double counting to the set of ordered pairs $(D_i, D_j)$ for which $D_i$ and $D_j$ shake hands with each other at the convention. Let $x_i$ be the number of times that $D_i$ shakes hands, and $y$ the total number of handshakes that occur. The number of pairs is $\sum_{i=1}^{n} x_i$. However each handshake gives rise to two pairs $(D_i, D_j)$ and $(D_j, D_i)$. So $\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 $n$ could be even and each $x_i$ could be even (e.g. $2+4+6+8 = 20$).

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

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

But we don't know what $x_i$ and $y_j$ are. We just know that they represent the number of pairs with the first component being $a_i$ and the second component being $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 $2+4+6+8 = 20$.

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

Let $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):

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

Applying the double-counting, each edge $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.

$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:

$\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 $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):

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

Applying the double-counting, each edge $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.

$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:

$\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 $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.