0
$\begingroup$

From Wiki Page of Degree (graph theory), we have

"The formula implies that in any undirected graph, the number of vertices with odd degree is even. This statement (as well as the degree sum formula) is known as the handshaking lemma. The latter name comes from a popular mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even."

Can we also say that,

in any group of people, the number of people who have shaken hands with an EVEN number of other people from the group is even."

This statement may seem obvious ?

So is it basically saying that: with an even number of people who have shaken hands, then number of people is is even in any group of people. (Understand it is a bit mouthful, is there any other more elegant way saying it besides Wiki Page and my own interpretation).

Q1: So it doesn't matter whether the number of people who have shaken hands is EVEN or ODD within any group, the number of people is even ?


Then trying to a better understanding from the Wiki Page of (Handshaking lemma). Then got confused by

In more colloquial terms, in a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands.

What does it even mean? (Let's say we have 5 parties of 2, 4, 6, 8, 10 people separately. And all people from each party shake hands with each other within each party. Then I believe 2 people party has 1 handshake( which is odd number), but for the rest, the party of 4 should have 6 handshakes, and the party of 6 should have 15 handshakes, and the party of 8 should have 28 handshakes.

Q2: Can someone please help me understand the colloquial terms statement better with some concrete examples ?

$\endgroup$
3
  • 2
    $\begingroup$ There is a difference between "the number of handshakes" and "adding up all the handshakes each person has performed". This distinction is at the heart of the proof of the handshake lemma. $\endgroup$
    – Arthur
    Jun 28 '20 at 6:43
  • $\begingroup$ In a group of $3$ people, if every pair shakes hands, then the number of people who have shaken hands with an even number of people is $3$, which is odd. $\endgroup$
    – quasi
    Jun 28 '20 at 6:54
  • $\begingroup$ More generally, if $n$ is odd, then for any group of $n$ people, since the number of people who have shaken hands an odd number of times is even, it follows that the number of people who have shaken hands an even number of times is odd. $\endgroup$
    – quasi
    Jun 28 '20 at 7:01
1
$\begingroup$

This statement is false

in any group of people, the number of people who have shaken hands with an EVEN number of other people from the group is even."

For the simplest example just take a party where no people shock hands. Zero is still an even number.

The handshake lemma is a direct consequence of the lemma that says the number sum of degrees of the vertices in a graph is double the amount of edges: Image of lemma

Now split the summation into two parts the sum of odd degrees call it O and the sum of even degrees call it E. We know that E + O = 2e which is an even number so they must either both be even or odd ,but E is always even since the sum of even numbers is always even. So The odd degrees must be of an even amount in order for us to obtain an even amount. ex: 1+1 = 2

This translates to the odd degreed vertices being in an even amount or that in a party there are an even number of people who have shaken odd hands.

$\endgroup$
2
  • $\begingroup$ I understand this part "We know that E + O = 2e which is an even number so they must either both be even or odd ,but E is always even since the sum of even numbers is always even. So The odd degrees must be of an even amount in order for us to obtain an even amount. ex: 1+1 = 2" but can you please elaborate this paragraph more "This translates to the odd degreed vertices being in an even amount or that in a party there are an even number of people who have shaken odd hands." ? $\endgroup$
    – user95432
    Jun 28 '20 at 14:29
  • $\begingroup$ O is the sum of the odd degrees in the graph meaning: O = v1 + v2 + v3 ... each Vi represents an odd vertex (a vertex with an odd degree) since we know that O is an even number and each Vi is an odd number this means that we have an even number of Vs in order for their sum to be even which is saying: we have an even number of odd vertices $\endgroup$
    – RAH
    Jun 28 '20 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.