# Combinatorics Ramsey Theory Proof

There are 9 passengers on a bus, some know each other. Among every 3 passengers there are two who know each other. Prove that there are at least 5 passengers, each of which knows at least 4 people on the bus.

• You can prove something a little stronger: either every passenger knows at least $4$ people on the bus, or else there are $5$ passengers who all know one another. – bof Apr 19 at 6:41
• How does the requirement that among every 3 passengers, there are 2 who know each other affect your solution? – Tcombinatorics Apr 19 at 8:03
• If some passenger knows at most $3$ other passengers, then there are $5$ passengers that he does not know. In that case, those $5$ people must all know one another; otherwise, there would be $3$ people, no two of whom know each other. – bof Apr 19 at 10:08
• Do you know of a way to prove this using ramsey theory? I understand the premise but am having a hard time discovering a proper proof. – Tcombinatorics Apr 19 at 10:12
• What's wrong with the proof I described in my previous comment? – bof Apr 19 at 10:18