1

I was given the following problem.

In a conference where n representatives attend, if 1 of any 4 of the attendants shake hands with the other 3, prove that 1 of any 4 of the attendants shake hand with the rest of the n − 1 attendants.

I'm familiar with the handshaking theorem and most of its applications but I'm not sure how to show in every random group of four, one must shake hands with everybody else.

Thanks.

ybs
  • 11
  • The earlier question uses is friends with instead of shakes hands with, but it’s the same question, and it has a very extensive hint. This question, which has two good answers, is also a duplicate. – Brian M. Scott Jan 10 '15 at 15:03

1 Answers1

1

Suppose this is not true. Pick a person $v$. He doesn't know someone (call him $w$). If $w$ does not know anyone we are done since if we pick $w$ and any other three persons no one will know $w$. Now pick a friend $x$ of $w$ such that $x$ knows $v$. (If no person exists who knows $w$ and $v$ we are also done since if we pick $v$,$w$ and any other two people none of them will know $v$ and $w$). So let $x$ know $v$ and $w$. Then there is a $y$ such that $x$ does not know $y$.

The set of vertices $v,w,x,y$ contradicts the hypothesis that given any four vertices one of them knows the other three. Since $u$ and $v$ don't know each other and $x$ and $y$ don't know each other.

Asinomás
  • 105,651