At a party among each group of four people there are three that all know each other or three that don't know each other. Acquaintances are mutual. Prove that all the participants at that party can be separated into two rooms so that in one room everybody knows everyone, and in the other room nobody knows anyone.
Solution
People and acquaintances can be represented by a complete graph in two colours, where the vertices represent people, blue edges connect people who know each other, and red edges connect people who don't know each other. We call a set with vertices a blue (red) -gon if all of the vertices are connected by a blue (red) edge. On the figures, red edges are represented by full lines, and blue edges by dashed lines.
Notice that the given condition implies that the graph contains a red or blue triangle (in the nontrivial cases where the graph has vertices).
Without loss of generality, we can assume that the graph contains a red triangle. Let us observe the largest red -gon. Let be the set of its vertices. If the remaining vertices are all connected by blue edges, we can place the people from in one room and everyone else in the other room, and the problem is solved.
We will show that the other case is not possible. Suppose there exist vertices connected by a red edge. Then there exists which is connected to by a blue edge, because otherwise we would have a red -gon. Analogously, there exists which is connected to by a blue edge.

We have two possibilities. If , then it is clear (see the left figure above) that no three of the vertices can form a monochromatic triangle, which is in contradiction with the initial condition.
On the other hand, suppose , for some . Let be an arbitrary vertex different from . The right figure represents the situation between vertices and . Clearly, in order to have a monochromatic triangle, must be connected to and by a red edge. So, and are connected by a red edge, and they are both connected by a red edge with every vertex from . But then is a red -gon, which is again in contradiction with the maximality of .