document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=4418>Question 4418</A>: <I><SPAN STYLE=\"word-break: break-all;\"> 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? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #2015 by </B><A HREF=/tutors/aboutme.mpl?userid=khwang><B>khwang(438)</B></A><img src=\"/images/stars/stars-10.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=khwang><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=2015\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> This question should belong to graph theory.<BR>\n" );
document.write( " A woman and her husband hosted a party for four other couples. The hostess asked everyone to shake <BR>\n" );
document.write( "hands and introduce themselves to each other. Of course, no one shook hands with his or her spouse. <BR>\n" );
document.write( "At some point, the hostess stopped them and asked each person how many hands he or she had shaken. <BR>\n" );
document.write( "Each person gave a different response. Whar was the response of her husband?<BR>\n" );
document.write( " Sol: Each person as a vertex and a shakehand means an edge between two vertices.<BR>\n" );
document.write( "      For each vertex v, the degree d(v) is the #  of vertices adjacent to v.<BR>\n" );
document.write( "      Let the 4 couples be (A,A'),(B,N'),(C,C') and (D,D'), the host and hostess be (H,H')<BR>\n" );
document.write( "      There are 10 vertices in the graph G.<BR>\n" );
document.write( "      Now we have the degrees of 9 persons except H' are all distinct. That means, the<BR>\n" );
document.write( "      nine possible degrees are 8,7,6,5,4,3,2,1,0.<BR>\n" );
document.write( "      Consider the vertex v, with d(v) = 8, this means v is adjacent to all other vertices except <BR>\n" );
document.write( "      v' (the spouse of v). But,if v  = H, then d(x) >= 1 for all eight vertex x in G-{H',v} and <BR>\n" );
document.write( "      so no vertices in G-{H'} is of degree 0, a contradiction. Hence, v cannot be the host H or<BR>\n" );
document.write( "      v is adjacent to H.  That is d(x)>=1 for all seven vertices x in G-{H',v,v'}.<BR>\n" );
document.write( "      So, the only vertex with degree 0 (in G-H') must be v'. Thus,we obtain a couple whose<BR>\n" );
document.write( "      degrees are 8 and 0 respectively. <BR>\n" );
document.write( "      For convenience, let this couple be A,A' and set d(A) =8,d(A') =0.<BR>\n" );
document.write( "      Next, consider the vertex of degree 7 in G-H', say d(B) = 7. We see that B is adjacent to<BR>\n" );
document.write( "      all other vertices except A' and B'. So, if v is in G-{H',A,A',B'}, then d(v) >= 2.<BR>\n" );
document.write( "      (since v must be adjacent to A and B). This implies d(B') = 1. So, we get a couple (B,B') <BR>\n" );
document.write( "      of degrees 7 & 1 respectively. <BR>\n" );
document.write( "     Similarly, consider the vertex u of degree 6 among other 5 vertices, Note,u is adjacent to<BR>\n" );
document.write( "  all other vertces except A',B',u'(its spouse). <BR>\n" );
document.write( "  d(A)=8 & d(B)=7 implies d(v) >= 2 for all v in G-{H',A,A',B,B') <BR>\n" );
document.write( "  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]<BR>\n" );
document.write( "  Hence, the only vertex with degree 2 must be u'.  Let this couple be (C,C') with degrees<BR>\n" );
document.write( "  6 , 2 respectively.<BR>\n" );
document.write( "    By the same argumenton the vertex of degree 5, the couple (D,D') has degree (5 ,3). <BR>\n" );
document.write( "  Therefore, the vertex with degree 4 must be the host and we obtain the number of shakehands of <BR>\n" );
document.write( "  the husband is 4. In fact, the wife also has same number,since she shakes with A,B,C,D(one with<BR>\n" );
document.write( "  each couple). <BR>\n" );
document.write( "  <BR>\n" );
document.write( "  Another way of proof: Let h' be the degree of H'in G<BR>\n" );
document.write( "  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<BR>\n" );
document.write( "  --> Delete the two vertices A,A', we get the the degree sequence (6,5,4,3,2,1,0,h'-1) in the <BR>\n" );
document.write( "  reduced graph G-{A,A'}--> Get a couple (B, B') of degree 6 & 0 in G-{A,A'} <BR>\n" );
document.write( "  --> Delete two more vertices B,B', we get the the degree sequence (4,3,2,1,0,h'-2) in the <BR>\n" );
document.write( "  reduced graph G-{A,A',B,B'}--> Get a couple (C, C') of degree 4 & 0 in G-{A,A',B,B'} <BR>\n" );
document.write( "  --> Delete two more vertices C,C', we get the the degree sequence (2,1,0,h'-3) in the <BR>\n" );
document.write( "  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'} <BR>\n" );
document.write( "  --> Delete two more vertices D,D', we get the the degree sequence (0,h'-4) =(0,0) in the <BR>\n" );
document.write( "  reduced graph G-{A,A',B,B',C,C',D,D'} = {H,H'} --> d(H) = 4 and d(H') = 4 in G.<BR>\n" );
document.write( "  <BR>\n" );
document.write( " Try to read carefully about the details or<BR>\n" );
document.write( " draw a graph to check.\r<BR>\n" );
document.write( "\n" );
document.write( " Kenny </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );