Prove that in a party of six people you can either find thre

Prove that in a party of six people you can either find three
people such that every one knows the other two, or you can find three people
such that no one knows the other two. We assume that if a person x knows a
person y then y knows x as well.

Solution

I think my favorite way of viewing this question is to think of a complete graph on six vertices (i.e. each vertex is connected to each other vertex), where all edges are colored either red or blue. Then you are to show that there is either a red triangle or a blue triangle.

You could put your reasoning on this picture, as it becomes very easy to follow.

Choose any one vertex; call it P. There are five edges leaving P. They are each coloured red or blue. The pigeonhole principle says that at least three of them must be of the same colour; for if there are less than three of one colour, say red, then there are at least three that are blue.

Let A, B, C be the other ends of these three edges, all of the same colour, say blue. If any one of AB, BC, CA is blue, then that edge together with the two edges from P to the edge\'s endpoints forms a blue triangle. If none of AB, BC, CA is blue, then all three edges are red and we have a red triangle, namely, ABC.