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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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