Problem 4

Seventeen people correspond by mail with one another, each with all the rest. In their letters only three different topics are discussed, and each pair of correspondents deals with only one topic. Prove that at least three people write to each other about the same topic.

Step 4 of 5: Apply the lemma

Previous step Next step

K_6\text{ uses at most two colors if no edge has color 1}

Detailed analysis

If an edge among those six vertices has color 1, it forms a color-1 triangle with $V_1$ . Otherwise the complete graph on the six vertices uses only the other two colors, so the two-color lemma supplies a monochromatic triangle.