Results 1 to 7 of 7

Math Help - Handshaking Lemma

  1. #1
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301

    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 ).
    Last edited by Sampras; May 29th 2009 at 09:52 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by Aryth View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by Aryth View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hensel's lemma
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 11th 2010, 06:26 PM
  2. gcd Lemma
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 2nd 2010, 06:24 PM
  3. Proof of a lemma
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 29th 2009, 05:19 AM
  4. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2009, 12:41 PM
  5. Ito's Lemma
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: June 25th 2008, 10:29 PM

Search Tags


/mathhelpforum @mathhelpforum