Prove that every edge-coloring of $K_{17}$ with $3$ colors contains a monochromatic $K_3$.

Question

Also, Prove that every edge-coloring of $K_6$ with $2$ colors contains at least two monochromatic copies of $K_3.$ I have no idea how to start these problems. What should I do?

Answer 1

Prove that every edge-coloring of $K_{17}$ with $3$ colors contains a monochromatic $K_3.$

Call the colors red, white, and blue. Consider a vertex $v.$ Of the $16$ edges incident with $v,$ there are at least $6$ of one color. We may assume that there are $6$ white edges incident with $v.$ Let $G$ be the subgraph induced by $6$ vertices which are joined to $v$ by white edges. If $G$ contains a white edge, that gives us a white triangle. If $G$ contains no white edges, then $G$ is a $K_6$ whose edges are colored red or blue, so it contains a monochromatic triangle by a theorem you already know.

Prove that every edge-coloring of $K_6$ with $2$ colors contains at least two monochromatic triangles.

Call the colors red and blue, and call the vertices $v_1,v_2,v_3,v_4,v_5,v_6.$ Let $r_i$ be the number of red edges and $b_i$ the number of blue edges incident with vertex $v_i.$ Note that $r_ib_i\le6,$ since $r_i+b_i=5.$

A "bichromatic angle" is a pair of different color edges meeting at a vertex. Since every bichromatic angle is in a bichromatic (i.e. not monochromatic) triangle, while every bichromatic triangle contains exactly two bichromatic angles, the number $N$ of bichromatic triangles is equal to half the number of bichromatic angles; thus $$N=\frac12\sum_{i=1}^6r_ib_i\le\frac12\sum_{i=1}^66=18.$$ Seeing as there are $\binom 63=20$ triangles all told, and at most $18$ of them are bichromatic, there must be at least $2$ monochromatic triangles.

P.S. The red-blue edge-colorings of $K_6$ with exactly $2$ monochromatic triangles are easily characterized. They are the colorings in which each vertex is incident with two edges of one color and three of the other; that is, the subgraph consisting of the blue edges has degree sequence $(2,2,2,2,2,2)$ or $(3,3,2,2,2,2)$ or $(3,3,3,3,2,2)$ or $(3,3,3,3,3,3).$