[Math] Coloring the vertices of $K_n$ and showing existence of a monochromatic triangle

coloringgraph theory

Looking for some hints on a homework problem. As far as I know, it's not from any textbook.

Color the vertices of $K_n$, the complete graph on $n$ vertices, red or blue. For how many $n$ will there be no monochromatic triangles (vertices all the same color). Note this question is not the one about coloring the edges.

My conjecture: for $n\ge 5$, there will always be a red or blue triangle.

I'm hoping the "pigeonhole principle" will apply somewhere. I don't think the instructor is asking us to delve into Ramsey theory.

Thanks in advance.

Best Answer

In the case that edges are irrelevant:

Your conjecture is completely correct. Here's how to apply the pigeonhole principle: with four vertices, there may be two of both colors. However, when you add a fifth vertex, it must be either red or blue, which forms a triangle with the other two of the same color. Another way to ask the same kind of question is how many integers does one need to have in order to have three even numbers or three odd numbers?

In the case that edges are relevant:

Your conjecture is almost correct. You can color the outside 5 lines forming a regular pentagon blue and the inner 5 lines (a star) red and yet not have a monochromatic triangle. However, it is true that for $K_n$ with $n \geq 6$ a monochromatic triangle WILL be forced.

Step 1: Take a vertex on $K_6$ and note that at least half of the lines from it must be one color or another. Now color three lines from it either color (say, blue).

Step 2: Apply pigeonhole principle; between the other vertices connected by a blue line to the first one, can the lines be blue or red?

Does that suffice?