Graph Theory Handshaking problem

Mr. and Mrs. Smith, a married couple, invited 9 other married couples to a party. (So the party consisted of 10 couples.) There was a round of handshaking, but no one shook hand with his or her spouse. Afterwards, Mrs. Smith asked everyone except herself, “how many persons have you shaken hands with?” All 19 answers were diﬀerent.

Unfortunately, when I try to simulate a smaller problem with 3 couples, I am getting that each couple is shaking 4 hands. Here is the diagram: As you can see both a1 and a2 have 4 blue lines each that are "attached" (ie they shake hands) to the other couples. Both b1 and b2 have 2 red lines and 2 blue lines. Do we count the blue lines again adding it to the 2 red lines giving us that b1 and b2 have 4 lines attached or do we just ignore the blue lines connecting to b1 and b2 and say that both b1 and b2 shake 2 hands each?

Both c1 and c2 also have 2 blue and 2 red lines. I meant to have blue lines designated for a1 and a2, and the red lines for b1 and b2. Does that mean that c1 and c2 have shaken 0 hands each? Or do I try another few lines attaching the c's to the a's and b's?

Another problem with the approach above is that each couple has the same number of handshakes even though that is not possible according to the question. I would appreciate any clarification on the question and what exactly am I doing wrong.

Thanks.

Here is a solution for two couples, $m_1,w_1$ and $m_2,w_2$. The edges are $(m_1,w_2),(w_1,w_2)$. The degrees are $1,1,0,2$ (in the order $m_1,w_1,m_2,w_2$).
Here is a solution for three couples, $m_1,w_1,m_2,w_2,m_3,w_3$. The edges are $(m_1,w_2),(w_1,w_2),(m_1,w_3),(w_1,w_3),(m_2,w_3),(w_2,w_3)$. The degrees are $2,2,1,3,0,4$.
• @user2635911 They are allowed to shake hands, but they don't have to. The question is formulated in a confusing way. What it really asks is for an undirected graph on $2n$ vertices, divided into $n$ groups of two vertices, in which two vertices forming a group are not connected, and for each $d \in \{0,\ldots,2n-2\}$, there is some vertex of degree $d$. Jun 8 '14 at 19:48