# In a group of 6 people either we have 3 mutual friends or 3 mutual enemies. In a room of n people?

A group of 6 people each pair is either a friend (acquaintance) or an enemy (stranger). It is to be proven that there are either 3 mutual friends or 3 mutual enemies in this group. I have an ad-hoc reasoning for this, but it is not yielding a big picture.

I would appreciate an approach or way of thinking about this which would make it easier to generalize it for n friends. i.e find the minimal number of mutual friends or enemies that can exist for a group of n people. My approach is getting cumbersome when I try for larger n.

(My reasoning) Any person either has (atleast 3 friends) OR (atleast 3 enemies). This is true because each person can be friend\enemy with five others and by the pigeonhole principle atleast one of the two holes (friend , enemy ) must contain 3 or more people. Consider one of the friends in the former case (or enemies in the latter). He has a relationship with the other two. There are three possibilities. FF, EE, EF. The first and last case results in 3 mutual friends. In the second case, we must consider the relationship between the remaining two. If they are friends, then there are three mutual friends. If they are enemies, then there are 3 mutual enemies.

-
This problem is part of Ramsey Theory; see also Wikipedia's page on the friends and strangers theorem – Arturo Magidin Jun 1 '11 at 19:05

The trouble is that this problem gets quite more difficult as you increase $n$. This problem (called the party problem) was discussed by Paul Erd\H{o}s himself in this video.