Question 4418
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