2
$\begingroup$

Question: At a party with $30$ people, $10$ know nobody there and the remaining $20$ people all know each other. Those who know each other greet with a hug, while those who do not greet with a handshake. After everyone has been introduced to everyone, how many handshakes have occurred?

Attempt: Since the $10$ people don't know anyone of the $20$ people who know each other, so each of these $10$ people shakes hand with each of these $20$ people, giving a total of $200$ handshakes. Also, since these $10$ people also shake hands among themselves, we get $\binom{10}{2}=45$ more handshakes. Thus, the total number of handshakes at this party is $245$.

Doubt: Since the number of handshakes is odd, does this not contradict the Handshaking Lemma? If not, what is wrong with my argument.

$\endgroup$
5
  • $\begingroup$ Could you state the handshaking lemma (there are two things often called the handshaking lemma) and how you have interpreted it? $\endgroup$ – Air Conditioner Jan 27 '18 at 23:03
  • 1
    $\begingroup$ You've counted total edges, not total valences. A person in the group of 10 each shake $29$ hands. The people in the twenty each shake $10$ hands. So the total is $10\cdot 29 + 20\cdot 10=490=2\cdot 245.$ $\endgroup$ – Thomas Andrews Jan 27 '18 at 23:03
  • $\begingroup$ In any event, the handshake lemma doesn't say the number of handshakes is even. $\endgroup$ – Thomas Andrews Jan 27 '18 at 23:06
  • $\begingroup$ The handshaking lemma says that in a graph, the number of vertices with odd degree is even. It say anything about the total number of edges. $\endgroup$ – Air Conditioner Jan 27 '18 at 23:06
  • $\begingroup$ @ThomasAndrews Thank you for clarifying my doubt. My interpretation of handshaking lemma was not correct. $\endgroup$ – Roby5 Jan 27 '18 at 23:08
5
$\begingroup$

This is not contradicting the Handshaking lemma. An even number of people (10) will shake hands an odd number of times (29). Another even number of people (20) will shake hands an even number of times (10).

I believe your confusion comes from the requirement in the Handshake lemma that the total sum here ($10\cdot 29+20\cdot 10=490$) is even. It is, and it is double your number (245) because, in your calculation, you did not count handshakes twice, unlike in the Handshake lemma calculation.

$\endgroup$
1
  • $\begingroup$ This was what I was looking for. Thank you $\endgroup$ – Roby5 Jan 27 '18 at 23:10
1
$\begingroup$

No, it doesn't contradict the Handshaking Lemma. Let's try to express this question with two set of vertices. Let $V_1$ and $V_2$ be two set of vertices with $|V_1| = 10$ and $|V_2| = 20$ (I think what these sets represent is understandable). Then for each handshake, we will have an edge between two vertices that shake hand. So, from $V_1$ to $V_2$, as you suggest, there are $200$ edges. Also we have $K_{10}$ component constructed by vertices of $V_1$ and it has $45$ edges.

Now, each vertex in $V_1$ has degree $29$ and each vertex in $V_2$ has degree $10$. So, sum of all degrees is $$29\cdot10+20\cdot10 = 490$$ Remember, Handshaking Lemma states

$$2e = \sum_{i=1}^nd(x_i)$$ where $e$ is the number of edges, $n$ is the number of vertices enumerated by $x_1$ to $x_n$.

So we have $$2\cdot245 = 490$$ which is true, so Handshaking Lemma still holds.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. $\endgroup$ – Roby5 Jan 27 '18 at 23:13
1
$\begingroup$

If we represent the problem with a graph where vertices represent people and an edge is present between two vertices if the two people know each other then we have a graph with 30 vertices, 10 of which are disconnected and the other 20 forming a complete graph $K_{20}$. In the complete subgraph we have $^{20}C_{2}=190$ edges and there are no edges incident to any of the 10 disconnected vertices (the people who know nobody) so the total number of edges in the graph is 190.

The degree of each of the vertices in the $K_{20}$ sub graph is 19 and the degree of each of the 10 disconnected vertices is 0. This gives a total degree of 20*19=380 which is equal to $2*|edges|=2*190=380$ so the problem does not contradict the handshake lemma.

Now for the number of handshakes we require the number of edges in the complement of our graph which is the 190 edges we initially had, subtracted from the number of edges in a $K_{30}$. This is equal to $^{30}C_{2}-190=435-190=245$ hence your attempt gives the correct solutions.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. $\endgroup$ – Roby5 Jan 27 '18 at 23:13

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.