Chromatic Triangles on a $K_{17}$ graph

If the edges of the complete graph $K_{17}$ (on 17 vertices with no three collinear) are each colored one of three colours can it be proven to have two or more monochromatic triangles?

Solution 1:

Yes. Choose one vertex. It has sixteen edges going out, so six of some color, say yellow. Now consider the $K_6$ composed of those six vertices. If it has no yellow edges, it has two monochromatic triangles and we are done. If it has two yellow edges, we have two monochromatic triangles and are again done. If it has only one yellow edge we have one monochromatic triangle. Now choose some vertex not involved in this argument-we have only used seven, so there are ten more. It must invoke at least one monochromatic triangle by the same argument.

Solution 2:

Yes, Sane & Wallis have proved in 1987 that there are at least 5 (!) monochromatic triangles in the 3-edge-colored K_17: see https://doi.org/10.1017/S0004972700026733. Optimal colorings which achieve this lower bound are known, as show the results of Al Zimmermann's Programming Contest "Monochromatic Triangles".