Theorem on friends and strangers

They might be meeting for the first time—in which case we will call them mutual strangers; or they might have met before—in which case we will call them mutual acquaintances.

It is convenient to phrase the problem in graph-theoretic language.

Let the edges be coloured red or blue depending on whether the two people represented by the vertices connected by the edge are mutual strangers or mutual acquaintances, respectively.

The theorem now asserts: Choose any one vertex; call it P. There are five edges leaving P. They are each coloured red or blue.

The utter simplicity of this argument, which so powerfully produces a very interesting conclusion, is what makes the theorem appealing.

We draw K5 as a pentagon surrounding a star (a pentagram).

Thus, 6 is the smallest number for which we can claim the conclusion of the theorem.