Consider all colorings of the edges of K6 such that every edge is either colored red or blue. Prove or disprove: there always exist at least two monochromatic triangles in any 2-coloring of the edges of K6.

So I have already proved using the pigeonhole principle that K6 must have at least one monochromatic triangle, so now I am wondering if it must also have two. I am currently trying to see if I can draw one without two monochromatic triangles, because that seems like it would be an easy way to disprove it, but that's getting very complicated.

I can't quite figure out where to go from here.


There are $\binom63=20$ triangles in $K_6$. We prove there are at least $2$ monochromatic triangles by showing that there are at most $18$ bichromatic ($2$-colored) triangles.

Let's use the term bichromatic angle to denote a pair of different-colored edges with a common endpoint. Note that every bichromatic triangle contains exactly $2$ bichromatic angles, and every bichromatic angle is contained in a unique bichromatic triangle. Thus the number of bichromatic triangles is exactly half the number of bichromatic angles.

Let $v_1,\dots,v_6$ be the vertices. Let $r_i$ be the number of red edges and $b_i$ the number of blue edges incident with $v_i$. Since $r_i+b_i=5$, the number of bichromatic angles meeting at $v_i$ is $r_ib_i\le6$; the total number of bichromatic angles is $\sum_{i=i}^6r_ib_i\le36$, the number of bichromatic triangles is $\frac12\sum_{i=1}^6r_ib_i\le18$, and the number of monochromatic triangles is at least $20-18=2$.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.