Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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