If there are six people in a room, must there be at least three of them who are either all friends with each other or all non-friends with each other? (If A is friends with B, then B is friends with A.) Explain.
Help
Solution
Arbitrarily choose one of the six people and label him/her A. For each of the remaining five people A is either a friend or he is not. If A is a friend then draw a black line between A and that person, and if he is not then draw a white line. We get 5 distinct lines connecting A to the other people in the room, and so by the pigeonhole principle 3 of them must be the same color. With no loss of generality we may assume 3 of them are black. Denote the other ends of these lines B,C,D. This gives an additional 3 lines BC, BD,CD. If even one of these lines is black then we can form a black triangle with A, which means there are 3 people at the party who are all friends. Otherwise the lines BC,BD,CD are all white and thus the triangle BCD is white, giving a group in which no one knows each other.