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?

  • $\begingroup$ 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. $\endgroup$ – Mark Bennet Sep 30 '18 at 16:15
  • $\begingroup$ Thanks, I'll edit now and suggest another proof that I came up with. $\endgroup$ – ekosman Sep 30 '18 at 16:42
  • $\begingroup$ 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. $\endgroup$ – Marcelo Campos Sep 30 '18 at 21:36
  • 1
    $\begingroup$ @Marcelo Campos I'm a little confused. What is k? Do you mean $r\cdot (f(k-1)-1)+2$ vertices? $\endgroup$ – ekosman Oct 1 '18 at 20:58
  • $\begingroup$ Yes, exactly, sorry for the confusing notation. $\endgroup$ – Marcelo Campos Oct 11 '18 at 19:38

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.


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.