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.

  • $\begingroup$ 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. $\endgroup$ – bof Apr 19 at 6:41
  • $\begingroup$ How does the requirement that among every 3 passengers, there are 2 who know each other affect your solution? $\endgroup$ – Tcombinatorics Apr 19 at 8:03
  • $\begingroup$ 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. $\endgroup$ – bof Apr 19 at 10:08
  • $\begingroup$ 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. $\endgroup$ – Tcombinatorics Apr 19 at 10:12
  • $\begingroup$ What's wrong with the proof I described in my previous comment? $\endgroup$ – bof Apr 19 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.