A Dinner Party Problem

This is a classic introductory result in combinatorics. Suppose that six people are gathered at a dinner party. Then there is a group of three people at the party who are either all mutual acquaintances or all mutual strangers.

To formalize this problem, consider the party as a complete graph on six vertices, as in the figure to the left. Each vertex represents a single guest, and each edge is colored by either blue, to represent that the connected vertices are acquaintances, or by yellow, to represent that the connected vertices are strangers. Then the result states that there exists a complete subgraph on three vertices with edges all the same color.

To see this, pick a vertex of the graph. Then because there are five edges going from this vertex to other vertices, there must be at least three edges which have the same color. Assume without loss of generality that the three edges are blue, as in the figure to the right. Then if there is a blue edge between any of the three vertices connected to the chosen vertex (vertices 3, 4 and 6 in the figure), then there is a complete same-colored subgraph, and the result holds.

So suppose instead that there are no blue edges between the three nodes. Then all three of the edges must be yellow, as in the figure to the left, and this forms a complete same-colored subgraph of the opposite color. Thus no matter the choice of coloring on the graph, we can find a same-colored complete subgraph on three vertices. As for the dinner party, we certainly can find a group of three people with the desired property, if we only care to look.