$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
Best Answer
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$.