Pigeonhole Principle Question - Group of 6 people, do 3 either know each other or not?

Question

Prove that in any group of 6 people there are always at least 3 people who either all know one-another or all are strangers to one-another.

Hint: Use the pigeonhole principle.

I don't see how this applies to the pigeonhole principle because I keep imagining a group of 4 strangers, and then 2 friends. This would be 6 total but against what the proof is asking. Maybe I don't understand the proof in question...

Answer 1

See Theorem on friends and strangers. The proof section gives precisely what you want and explains how the pigeonhole principle is used here.

Answer 2

This can be seen as the Ramsey number $R(3,3)$ , and we know that $R(3,3)=6$. The Ramsey number $R(s,t)$ can be seen as the least number R so that a $K_r$ graph painted of 2 colors ; say colors A and B, contains either a $K_s$ of color A, or a $K_t$ subgraph of color B .

To illustrate the situation, draw a $K_6$ graph, i.e., a complete graph on $6$ vertices (a graph on 6 vertices where any two vertices are joined by an edge), and join any two vertices with, say, a red edge if two people know each other, and join them with/by a blue vertex otherwise. Fix a given vertex x. Then there are , by the pigeonhole principle, at least $3$ blue ( can also be red) incident with x....Can you continue from here?