# Monochromatic triangle and edge colouring

$r(k) := R(\underbrace{3,3,...,3}_k)$

(I.e. $r(k)$ is the minimum integer $n > 0$ such that every coloring of edges of $K_n$ in $k$ colors is guaranteed to produce a monochromatic triangle.) Show that for $k \ge 2$

$$r(k) \le k\big(r(k−1)−1\big) + 2$$

Can anyone help with this? Any hints are welcome! Thanks

-
this is third problem in a very short amount of time that you have asked a question about the coloring of graphs. Is this homework? What work have you done on your own? – Jebruho Nov 4 '12 at 22:45
Also, if you are going to be a regular here, you're contributions will look much better if you learn how to format them properly. See, e.g., meta.math.stackexchange.com/questions/107/… and meta.math.stackexchange.com/questions/5020/… and meta.math.stackexchange.com/questions/1773/… – Gerry Myerson Nov 4 '12 at 22:51
no, these are practice questions off the internet to study for a midterm. i've done some successfully, however i posted those which i wasn't able to do and looked topical to what's been covered in class. Ramsey theory is pretty much the one thing I'm having an insane amount of trouble with. i dont even know where to begin and there aren't enough corrected exercises online. – Gogol Nov 4 '12 at 23:03
alright, i got this one as a recursion and got an inequality out of it. thanks anyway! – Gogol Nov 5 '12 at 0:10

Assume we have a complete graph on $k(r(k-1)-1)+2$ vertices and $k$ edge colours [I am European]. Choose an arbitray vertex $v$. Divide the other $k(r(k-1)-1)+1$ vertices according to colour that connects them to $v$. At least one of these $k$ sets must have $r(k-1)$ vertices. The vertices in this set are all connected to $v$ by the same colour. That colour cannot be used between the vertices in that set (or else we find a triangle). So the set is internally coloured with $k-1$ colours, and must contain a monochromatic triangle.
This proof is very similar to the classic one that shows that $R(3,3,3) \le 17$, based on $R(3,3)=6$.