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 different.

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.



1 Answer 1


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$.

Hopefully you can generalize this construction to an arbitrary number of couples. If not, you can always try running the Havel–Hakimi algorithm, trying to avoid connecting a husband to his wife.

  • $\begingroup$ Why don't w1 and m2 shake hands? According to the question, the only restriction is that a person cannot shake hands with his or her spouse. According to that rule, w1 and m2 should be allowed to shake hands. $\endgroup$ Jun 8, 2014 at 19:25
  • 3
    $\begingroup$ @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$. $\endgroup$ Jun 8, 2014 at 19:48
  • $\begingroup$ Ahh I think I understand the question now. The restrictions are that each person cannot shake their spouse's hand and that all the answers Mrs.Smith got from everyone else is different. In this case there are 10 couples (20 people). The maximum number of hands shaken is 18 and the sum of the number of handshakes by each couple must be equal (in this case it is 18). So Mr and Mrs. Smith have both shaken 9 hands each. $\endgroup$ Jun 8, 2014 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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