Suppose that the edges of K17 are colored using three colors

Suppose that the edges of K_17 are colored using three colors. Prove that there exists a monochromatic triangle.

Solution

Let there be given an edge coloring of K₁₇ with the three colors red, blue, and green. Since there is no 5-regular graph of order 17, some vertex v of K₁₇ must be incident with six edges that are colored the same, say

vv_i (1 i 6) are colored green.

Let H = K₆ be the subgraph induced by {v1,v2,...,v6}. If any edge of H is colored green, then K₁₇ has a green triangle. Thus we may assume that no edge of H is colored green. Hence every edge of H is colored red or blue. Since H = K₆ and R(3,3) = 6 , it follows that H and K₁₇ as well contain either a red triangle or a blue triangle. Therefore, K₁₇ contains a monochromatic triangle.