title can't exactly capture the description of this problem so well. Here's the question in full:
"At a convention, any group of four people contains one who knows the other three. Prove there is someone at the convention who knows everyone else."
I've tried to prove this inductively, but am not sure whether or not that is the correct way to go about it.
Induction Hypothesis: Assume that there is someone at the convention who knows everyone else, given that any group of four people contains one who knows the other three (assume this is true given $n$ people).
Basis case: there are four people at the convention. Therefore, there is one in this group of four who knows the other three (everyone else at the convention).
Induction step: Prove this is true for $n+1$ people. We see that this is the same as inserting one more person into a convention with $n$ people, where there must be someone who knows everyone. Therefore, we only need to show that this person who knows everyone also knows the $n+1$th person we're inserting. And I'm stuck.
If anyone could help me out here, that would be greatly appreciated. Thanks!