Any group of six people must contain at least three mutual friends or three mutual strangers.

Represent the people with dots, and connect friends with blue lines and strangers with red. Will the completed diagram always contain a red or a blue triangle?

Because A has five relationships and we’re using two colors, at least three of A’s connections must be of the same color. Say they’re friends:

Already we’re perilously close to completing a triangle. We can avoid doing so only if B, C, and D are mutual strangers — in which case they themselves complete a triangle:

We can reverse the colors if B, C, and D are strangers to A, but then we’ll get the complementary result. The completed diagram must always contain at least one red or blue triangle.

I think this problem appeared originally in the William Lowell Putnam mathematics competition of 1953. Six is the smallest number that requires this result — a group of five people would form a pentagon in which the perimeter might be of one color and the internal connections of another.

(Update: In fact the more general version of this idea was adduced in 1930 by Cambridge mathematician F.P. Ramsey. It is very interesting.) (Thanks, Alex.)