Six Hollywood stars form a social group that has very special characteristics. Every distinct pair of stars in the group either mutually love each other or mutually hate each other. There is no set of three individuals who mutually love one another. Prove that there is at least one set of three individuals who mutually hate each other. The problem leads into a fascinating field of graph theory, blue-empty chromatic graphs, the nature of which will be explained alongside the answer.
Every two people in a set of six people either mutually love or mutually hate each other, and there is no set of three who mutually love one another. The problem is to prove that there is a set of three who mutually hate one another.
The problem is easily solved by a graph technique. Six dots represent the six individuals in the illustration here:
All possible pairs are connected by a broken line that stands for either mutual love or mutual hate. Let blue lines symbolize love and red lines symbolize hate. Consider dot A. Of the five lines radiating from it, at least three must be of the same color. The argument is the same regardless of which color or which three lines we pick, so let us assume that three lines are red as shown in the illustration. If the lines forming triangle BCE are all blue, then we have a set of three people who mutually love one another. We are told no such set exists; therefore at least one side of this triangle must be red. No matter which side we pick for red, we are sure to form an all-red triangle (i.e., three people who mutually hate one another). The same result is obtained if we choose to make the first three lines blue instead of red. In that case the sides of triangle BCE must all be red; otherwise a blue side would form an all-blue triangle. In brief, there must be at least one triangle that is either all-blue or all-red. The problem rules out an all-blue triangle, so there must be an all-red one.
A stronger conclusion is actually obtainable. If there is no all-blue triangle, it can be shown (by more complicated reasoning) that there are at least two all-red triangles. In graph theory, a two-color graph of this sort—with no blue triangles—is called a blue-empty chromatic graph.
If the number of points is six, as in this problem, the minimum number of red triangles is two. When the number of points in a blue-empty graph is less than six, it is easy to draw such graphs with no red triangles. When the number of points is seven, there must be at least four red triangles. For an eight-point blue-empty graph the minimum number of red triangles is eight; for a nine-point graph it is 13. Anyone wishing to go deeper into the theory should consult Gary Lorden’s excellent paper “Blue-Empty Chromatic Graphs” in the February 1962 issue of The American Mathematical Monthly.
We’d love to hear from you! E-mail us at games@sciam.com to share your experience.
A version of this puzzle originally appeared in the October 1962 issue of Scientific American.