Suppose you have a room with 6 people. Show that there exists some three people, all whom know each other, or three people all of whom are not acquainted with each other.

This is a classic problem in Ramsey Theory. The solution goes as follows. Suppose you represent every person as a point. Connect two people with a red line if they know each other, and connect two people with a blue edge if they are strangers with each other.

In the mathematical lingo, this is representing our problem as a graph, where every person is represented by a vertex, or point, and we connect every pair of people with an edge.

The status of knowing or not knowing someone is represented by how you color the edge, red for knowing, blue for not knowing. We want to show that there must exist three people all of whom know each other, or three people all of whom are strangers with each other.

This corresponds to finding three points, whose pairwise connections are either all red, or all blue. We call a set of vertices all of whose pairwise connections are the same color monochromatic. So what we are looking for is a monochromatic red triangle or a monochromatic blue triangle.

Now let’s focus on one person. Call her Alice. By the Pigeonhole Principle, she must either know at least three other people, and be strangers with at most 2 of the other people in the room, or she must be strangers with at least 3 other people, and know at most 2 other people.

Suppose she knows at least three other people in the room, call them Bob, Carol, and Dave. Then if Bob, Carol, and Dave all pairwise do not know each other, then they form a stranger triangle. Else, at least two of Bob, Carol, and Dave know each other, and then they would form a friendship triangle with Alice! In either case, we have found a red knowing triangle or a blue stranger triangle!

The case where Alice is strangers with at least 3 people is similar – you just switch the status of knowing to being strangers with, and vice versa.

So with 6 people, we have guaranteed the existence of either a friendship triangle or a stranger triangle. Can we do this with fewer people? With 5 people, if every person is either friends or strangers with every other people, can we guarantee the existence of a red triangle or a blue triangle?

It turns out that with 5 people, we can draw the friendship graph with no red triangle and no blue triangle: Arrange the five people in a pentagon. Color the sides of the pentagon blue, and color the diagonals of the pentagon red. Then, no matter which three vertices you pick, the edges will not be monochromatic.

We say that R(s,t) is the minimum number of vertices in a graph such that with there exists a monochromatic set of s vertices (people), all of whom know each other, or a set of t vertices (people), all of whom are strangers with each other. In other words, if we two color the edges of a graph on R(s,t) vertices red and blue, then must there must exist either a red monochromatic complete graph on s vertices or a blue monochromatic graph on t vertices.

So what we’ve shown is that R(3,3) > 5 and R(3,3) is at most 6, so R(3,3) must be equal to 6.