A party contradicting Handshaking Lemma

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.