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