People on the train, prove 3 people know each other or don't know each other.

Question

There are 6 people on the train. Prove that there are 3 people among them that know each other or don't know each other.

My first instinct is that it might have to do something with a bipartite graph, but this seems not to work at all with 3 of them knowing each other.

But I still don't have an idea how to do this.

Answer 1

Choose a guy. This guy either know or do not know at least $3$ of the remaining $5$ (pigeon hole principle). Say he does not know $3$ of them.

If any $2$ of these $3$ guys does not know each other, our first guy and these $2$ guys do not know each other.

If these $3$ guys know each other, then we have $3$ guys knowing each other.