Q: Prove that $r_{k+1}(3) \leq (k+1)( r_k(3) - 1) + 2$ I'm tasked to prove that $r_{k+1}(3) \leq (k+1) (r_k(3) - 1) + 2$ and then use the result to come up with an upper bound for $r_n(3)$.
I'd appreciate a bit of a walkthrough, as I've had a hard time with this.

A: HINT: Suppose that we have an edge coloring of $K_n$ with $k+1$ colors that has no monochromatic triangle. Let $v_0$ be a vertex of the graph, and for $i=1,\ldots,k+1$ let $N_i$ be the set of vertices connected to $v_0$ by an edge of color $i$.

*

*Show that for each $i$, no two vertices in $N_i$ can be connected by an edge of color $i$. Conclude that the complete subgraph induced by $N_i$ is edge-colored with $k$ colors and has no monochromatic triangle.

*What is the maximum possible number of vertices in $N_i$?

*What is the maximum possible number of neighbors of $v_0$?

*What is the maximum possible value of $n$?


A: To prove the given inequality, you should recall the proof that $r(3,3)\le 6$, and try a similar strategy. For example, to prove that $r(3,3,3)\le 3\cdot (r(3,3)-1)+2=17$, consider a particular vertex, $v$ in a graph whose edges are colored red, blue and green. Since $v$ is the endpoint of $16$ edges, there must be some color for which $v$ is the endpoint of $\lceil 16/3\rceil =6$ edges of that color. WLOG the color is red, and let $S$ bet the set of vertices joined to $v$ by a red edge. There are then two cases:

*

*If any two vertices $w$ and $u$ in $S$ are connected by a red edge, then $\{u,v,w\}$ is a red triangle.


*Otherwise, $S$ is only joined together by blue and green edges. Since $6\ge r(3,3)$, there must be either a blue or red triangle.
You need to generalize that argument to all $k$. Instead of using $\lceil 16/3\rceil =6$, you will use
$$
\left\lceil (k+1)(r_k(3)-1)+1 \over k+1 \right\rceil=r_k(3)
$$

For an upper bound on $r_k(3)$, I will use a weaker form of the inequality you were tasked to prove:
$$
r_{k+1}(3)\le (k+1)r_k(3)$$
You can apply this repeatedly to get a non-recursive bound on $r_k(3)$. For example, shortening $r_k(3)$ to $r_k$:
\begin{align}
r_5
  &\le 5\cdot r_4
\\&\le 5\cdot 4\cdot r_3 
\\&\le 5\cdot 4\cdot 3\cdot r_2
\\&\le 5\cdot 4\cdot 3\cdot 2\cdot r_1 
\\&=   5\cdot 4\cdot 3\cdot 2\cdot 3
\\&=   5!\cdot 3
\end{align}
Generalizing this pattern, you can prove $r_k(3)\le 3\cdot k!$. You can get a better upper bound by using the full inequality instead of the simplified, but it will be messier.
