Party Problem

Suppose there are six people at a party. Prove that there are always three of them so that every two know each other (or) no two know each other.

In other words, let the edges of the complete graph on six vertices (\(K_6\)) be colored with two colors : red or blue. For any such coloring, prove that there is always a monochromatic triangle.

Show that on \(K_5\) there exist such bichromatic edge colorings without monochromatic triangles.

Source: folklore




Consider any single vertex \(v\) of \(G\). Since \(G\) is complete, \(v\) must have degree \(5\). It immediately follows that we must have at least three adjacent edges of either color. Without loss of generality, suppose that this color is blue. Then there are at least three vertices \(u_1\), \(u_2\), \(u_3\) such that any blue edge between a \(u_i\) and \(u_j\) would cause triangle \(v,u_i,u_j\) to be monochromatic. However, if no such blue edge exists, then the triangle \(u_1,u_2,u_3\) only contains red edges and is also monochromatic. By contradiction, it follows that there must always be a monochromatic triangle in a complete graph with six vertices.

The following edge-coloring of \(K_5\) has no monochromatic triangles.

enter image description here

Related Content