Theorem on friends and strangers

The theorem on friends and strangers is a mathematical theorem in an area of mathematics called Ramsey theory.

Suppose a party has six people. Consider any two of them. 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. The theorem says:

A proof of the theorem requires nothing but a three-step logic. It is convenient to phrase the problem in graph-theoretic language.

Suppose a graph has 6 vertices and every pair of (distinct) vertices is joined by an edge. Such a graph is called a complete graph (because there cannot be any more edges). A complete graph on ${\displaystyle n}$ vertices is denoted by the symbol ${\displaystyle K_{n}}$.

Now take a ${\displaystyle K_{6}}$. It has 15 edges in all. Let the 6 vertices stand for the 6 people in our party. 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:

...
Wikipedia