SOLUTION: A woman and her husband hosted a party for four other couples. The hostess asked everyone to shake hands and introduce themselves to each other. Of course, no one shook hands wit

Question 4418: A woman and her husband hosted a party for four other couples. The hostess asked everyone to shake hands and introduce themselves to each other. Of course, no one shook hands with his or her spouse. At some point, the hostess stopped them and asked each person how many hands he or she had shaken. Each person gave a different response. Whar was the response of her husband?
Answer by khwang(438) (Show Source): You can put this solution on YOUR website!
This question should belong to graph theory.
A woman and her husband hosted a party for four other couples. The hostess asked everyone to shake
hands and introduce themselves to each other. Of course, no one shook hands with his or her spouse.
At some point, the hostess stopped them and asked each person how many hands he or she had shaken.
Each person gave a different response. Whar was the response of her husband?
Sol: Each person as a vertex and a shakehand means an edge between two vertices.
For each vertex v, the degree d(v) is the # of vertices adjacent to v.
Let the 4 couples be (A,A'),(B,N'),(C,C') and (D,D'), the host and hostess be (H,H')
There are 10 vertices in the graph G.
Now we have the degrees of 9 persons except H' are all distinct. That means, the
nine possible degrees are 8,7,6,5,4,3,2,1,0.
Consider the vertex v, with d(v) = 8, this means v is adjacent to all other vertices except
v' (the spouse of v). But,if v = H, then d(x) >= 1 for all eight vertex x in G-{H',v} and
so no vertices in G-{H'} is of degree 0, a contradiction. Hence, v cannot be the host H or
v is adjacent to H. That is d(x)>=1 for all seven vertices x in G-{H',v,v'}.
So, the only vertex with degree 0 (in G-H') must be v'. Thus,we obtain a couple whose
degrees are 8 and 0 respectively.
For convenience, let this couple be A,A' and set d(A) =8,d(A') =0.
Next, consider the vertex of degree 7 in G-H', say d(B) = 7. We see that B is adjacent to
all other vertices except A' and B'. So, if v is in G-{H',A,A',B'}, then d(v) >= 2.
(since v must be adjacent to A and B). This implies d(B') = 1. So, we get a couple (B,B')
of degrees 7 & 1 respectively.
Similarly, consider the vertex u of degree 6 among other 5 vertices, Note,u is adjacent to
all other vertces except A',B',u'(its spouse).
d(A)=8 & d(B)=7 implies d(v) >= 2 for all v in G-{H',A,A',B,B')
and so d(v) >= 3 for all v in G-{H',A,A',B,B',u,u')[Note v is adjacent to A, B and u]
Hence, the only vertex with degree 2 must be u'. Let this couple be (C,C') with degrees
6 , 2 respectively.
By the same argumenton the vertex of degree 5, the couple (D,D') has degree (5 ,3).
Therefore, the vertex with degree 4 must be the host and we obtain the number of shakehands of
the husband is 4. In fact, the wife also has same number,since she shakes with A,B,C,D(one with
each couple).

Another way of proof: Let h' be the degree of H'in G
Consider the degree sequence (8,7,6,5,4,3,2,1,0,h) in G--> Get a couple (A,A') of degree 8 & 0 in G
--> Delete the two vertices A,A', we get the the degree sequence (6,5,4,3,2,1,0,h'-1) in the
reduced graph G-{A,A'}--> Get a couple (B, B') of degree 6 & 0 in G-{A,A'}
--> Delete two more vertices B,B', we get the the degree sequence (4,3,2,1,0,h'-2) in the
reduced graph G-{A,A',B,B'}--> Get a couple (C, C') of degree 4 & 0 in G-{A,A',B,B'}
--> Delete two more vertices C,C', we get the the degree sequence (2,1,0,h'-3) in the
reduced graph G-{A,A',B,B',C,C'}--> Get a couple (D, D') of degree 2 & 0 in G-{A,A',B,B',C,C'}
--> Delete two more vertices D,D', we get the the degree sequence (0,h'-4) =(0,0) in the
reduced graph G-{A,A',B,B',C,C',D,D'} = {H,H'} --> d(H) = 4 and d(H') = 4 in G.

Try to read carefully about the details or
draw a graph to check.
Kenny
RELATED QUESTIONS
In a party 15 people shake their hands with each other. How many times did the hand-shake (answered by solver91311)

Five couples are to eat at a round table with men and women in alternate seats. If the... (answered by ikleyn)

A dinner party has 7 couples. The hostess wishes to seat all the guests around a circular (answered by edjones)

If there are 12 persons in a party and each of them shake hands with all others.What is... (answered by ikleyn)

1 - How many handshakes can take place if there are 100 people and no one shakes hands... (answered by khwang)

5 women and 4 men are at a party. Each person shakes hands with each other person in... (answered by ikleyn)

You are in a roomful of 40 people. Everyone is asked to shake hands with everyone. How... (answered by jorel1380)

find the number of ways to seat n married couples around a table in the following cases (answered by galactus)

There was a party and everyone shook everyone's hands. There were 66 handshakes!! How... (answered by MathLover1)