Every clique with 17 vertices which it's edges are colored with 3 different colors must have monochromatic triangle

629 Views Asked by At

I tried to solve this problem, but I'm not sure I got it right. The question proposes a hint:

Let G be a clique with 6 vertices which it's edges are colored with 3 different colors, then there's a monochromatic triangle in G.

This is my suggestion:

Let $G=(V,E)$ and $v_1\in V$. $G$ is a clique with 17 vertices, hence there are 16 edges from $v_1$. There are 3 colors, hence there are at least $\lceil16 / 3\rceil=6$ edges with the same color from $v_1$, say Blue.

Now consider the vertices $\{v_2,...,v_7\}$, neighbors of $v_1$. These are 6 vertices in this group and they perform a clique with 6 vertices. If the edges between them are colored with only 2 colors, we're done, since every clique with 6 vertices and 2 colors of edges have a monochromatic triangle. Otherwise there are 3 colors, and we can conclude that there's an blue edges, say $(v_i,v_j)$ for $i\ne j \in {2,...,7}$. Notice we got the blue triangle: $v_1 - v_i - v_j$.

Is there any problem with this proof?

1

There are 1 best solutions below

0
On

I think your proof is fine; however it is useful to know that this is a small example of what is a larger class of problems. These are numbers called Ramsey numbers, and here you prove that $R(3,3,3)$ is $17$. You might want to check out Chromatic Triangles on a $K_{17}$ graph and this. I personally find them fascinating and they're a somewhat celebrated topic.