BMAD Posted July 29, 2016 Report Share Posted July 29, 2016 Let’s say there is a gathering where among any three people there are two friends. Is it true that people at such gathering can always be divided into two groups in a way that every two people in one group are friends? Quote Link to comment Share on other sites More sharing options...
0 Logophobic Posted July 31, 2016 Report Share Posted July 31, 2016 Spoiler This appears to be an example of the monochromatic triangle problem and its connection to Ramsey's theorem Specifically, in any group of at least six persons, there will be a subgroup of at least three persons in which there are either no friendships (a scenario excluded by the question) or each person in the subgroup is friends with each other person in the subgroup (the scenario that the question wants to prove is implied by the exclusion of the former). To answer the question, yes it is true. Quote Link to comment Share on other sites More sharing options...
Question
BMAD
Let’s say there is a gathering where among any three people there are two friends. Is it true that people at such gathering can always be divided into two groups in a way that every two people in one group are friends?
Link to comment
Share on other sites
1 answer to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.