Question:
Consider a group of 8 people, each pair of which are either friends or enemies. Show
that if some person in the group has at least 6 friends, then there are 4 people who
are mutual friends or 3 people who are mutual enemies.
My approach (totally wrong and I have no idea why..):
We know that there is one person who has at least 6 friends; that is to say, we can consider this problem in 2 cases.
When this person has 7 friends:
In this case, we can just temporarily ignore this person since he is a friend with everyone. Considering a complete graph of 7 persons, R(k, l) = 7. By checking the table we know that k, l = 2 and 7, which means in the group without this person, there are 2 mutual or 7 mutual enemies, or 7 mutual friends or 2 mutual enemies. Now put this person back in: there are 3 mutual or 7 mutual enemies, or 8 mutual friends or 2 mutual enemies since the previously ignored person is friend with everyone.
When this person has 6 friends:
………
I have realized that my approach was wrong after the first case above. However, I still think it kind of makes sense.
Helps with details are appreciated!
Best Answer
Take complete graph $K_8$ on $8$ vertices, whose edges are colored red, if two vertices $\{i,j\}$ are friends, and blue, if $\{i,j\}$ are enemies. Looking at one person $v$ in particular, who has $6$ friends within the group.
These 6 people he is friends with now make up a complete graph $K_6$ on $6$ vertices. As suggested in the comments, this graph is known to have either a red $K_3$ or a blue $K_3$, since $R(3,3)=6$. Therefore there is either a blue triangle, in which case we'd be done, or there is a red triangle. In the event that there is a red triangle, it joins with the vertex that wasn't friends with our original $v$. Therefore we are done.