# Showing that $K_7$ contains at least 4 monochromatic triangles

A problem in my book is:

Let the edges of $K_7$ be colored with the colors red and blue. Show that there are at least four subgraphs $K_3$ with all three edges the same color (monochromatic triangles). Also show that equality can occur.

By the theorem on friends and strangers it is clear that 1 monochromatic triangle exists. Deleting a vertex of that triangle and applying the theorem again yields another. Why are two more guaranteed?

As an aside, a result in my book states that the number of monochromatic triangles in a 2-colored $K_n$ is at least $\binom{n}{3}-\lfloor \frac{n}{2}\lfloor (\frac{n-1}{2})^2 \rfloor \rfloor$. I want to demonstrate my solution without applying this result though as it appears later on in the book.

Thank you for your time.

## 1 Answer

A "biangle" is a triple of vertices $(a,b,c)$ where the edge joining $a$ to $b$ is not the same color as the edge joining $b$ to $c$. We call $b$ the "apex" of the biangle.

A vertex with 3 red and 3 blue edges is the apex of 9 biangles; any other color distribution leads to fewer biangles. Thus, the whole graph has at most 63 biangles.

If a triangle is not monochromatic, it has exactly 2 biangles. So the graph has at most 31 non-monochromatic triangles.

But the graph has 35 triangles, so it has at least 4 monochromatic triangles.