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

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?

• If you have a clique of six which is coloured with TWO colours, you get a monochromatic triangle. Whether a triangle is monochromatic or not depends on specifics of the colouring - you haven't justified that the $180$ triangles are evenly split between different colourings. In fact you could colour the edges from clique A to clique B with colour $1$, from B to C with colour two and from C to A with colour $3$. Then all your 180 triangles are identically coloured with one side of each colour, and none is monochromatic. – Mark Bennet Sep 30 '18 at 16:15
• Thanks, I'll edit now and suggest another proof that I came up with. – ekosman Sep 30 '18 at 16:42
• I think the proof is OK now, try to generalize it, to prove that if for every coloring of a clique with $f(r-1)$ vertices with $r-1$ color there is a monochromatic triangle, then for every coloring of a clique with $r(f(k-1)-1)+2$ vertices with $r$ colors there is a monochromatic triangle :D. – Marcelo Campos Sep 30 '18 at 21:36
• @Marcelo Campos I'm a little confused. What is k? Do you mean $r\cdot (f(k-1)-1)+2$ vertices? – ekosman Oct 1 '18 at 20:58
• Yes, exactly, sorry for the confusing notation. – Marcelo Campos Oct 11 '18 at 19:38

## 1 Answer

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.