5. In class we showed that at any party with 6 people there is either a col lect

Question

5. In class we showed that at any party with 6 people there is either a col lection of 3 who are mutual friends or a collection of 3 who are muutual enemies. Actually one can say a bit more, namely there are either at least two groups of 3 mutual friends, at least two groups of 3 mutual enemies, or at least one group of 3 mutual friends and at least one group of 3 mutual enemies. This problem will walk you through a proof of this. Consider a party with 6 people (a) Explain why we can assume without loss of generality that 1,2, 3 are mutual friends. (b) Explain why if one of 1,2,3 has at least two friends outside of 1,2,3 we are done.

Explanation / Answer

(a) Because we can just assume 1 2 and 3 as names of the persons which are random and generality is not being lost here

(b) if one of 1,2,3 has atleast two friends outside of 1,2,3 then the other two of 1,2,3 will be his enemies, which means these are the three mutual enemies among themselves

(c) if one of 1,2,3 has no friends implies all of his 2 friends in 1,2,3 which implies 1,2,3 are mutual friends and hence we are done

(d) if 4,5,6 are mutual friends, 1,2 3 will be mutual enemies and we are done

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.