(i) prove that $\displaystyle r(a, b, 2) = r(a, b)$
(ii) prove that $\displaystyle r(a, b, c) \leq r(a - 1, b, c) + r(a, b - 1, c) + r(a, b, c - 1) - 1$
(iii) use parts (i) and (ii) to show that $\displaystyle r(3, 3, 3) \leq 17$
sorry...
$\displaystyle r(m, n)$ denotes a Ramsey number. It is the least positive integer $\displaystyle p$ such that for any graph $\displaystyle G$ on $\displaystyle p$ vertices:
• either $\displaystyle G$ contains a copy of $\displaystyle K_{m}$,
• or else $\displaystyle \overline{G}$ contains a copy of $\displaystyle K_{n}$.
Note $\displaystyle G \cup \overline{G} = K_{p}$ so we may restate the definition as: $\displaystyle r(m, n)$ is the least positive integer $\displaystyle p$ such that if we 2-colour the edges of $\displaystyle K_{p}$ then either we have a mono-chromatic $\displaystyle K_{m}$ or a mono-chromatic $\displaystyle K_{n}$.
Hi there
(i) Let G be a complete graph on $\displaystyle r(a,b)$ vertices and let G be coloured with white, red and blue. If there is at least one edge coloured with blue then this edge is a blue $\displaystyle K_2$. If there's no blue edge then whole G is coloured with white and red, so it contains white $\displaystyle K_a$ or red $\displaystyle K_b$. We conclude that $\displaystyle r(a,b,2) \leq r(a,b)$.
On the other hand, let H be a complete graph on $\displaystyle r(a,b,2)$ vertices. If we colour it with white and red only, it has to contain white $\displaystyle K_a$ or red $\displaystyle K_b$. So $\displaystyle r(a,b) \leq r(a,b,2)$.
(ii) Let $\displaystyle n = r(a-1,b,c) + r(a,b-1,c) + r(a,b,c-1) - 1$ and assume the edges of $\displaystyle K_n$ are coloured white, red and blue. Arbitrarily pick one vertex $\displaystyle v$ and consider its $\displaystyle n-1$ edges. We have: The number of white edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a-1,b,c)$ OR the number of red edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a,b-1,c)$ OR the number of blue edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a,b,c-1)$. Can you see why?
Spoiler:
So we distinguish three cases:
1) the number of white edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a-1,b,c)$,
2) the number of red edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a,b-1,c)$,
3) the number of blue edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a,b,c-1)$.
In case 1) we can choose exactly $\displaystyle r(a-1,b,c)$ vertices connected to $\displaystyle v$ by a white edge. These chosen vertices induce complete subgraph. This subgraph contains a white $\displaystyle K_{a-1}$ or a red $\displaystyle K_b$ or a blue $\displaystyle K_c$ (because it has $\displaystyle r(a-1,b,c)$ vertices). In the first case, vertex $\displaystyle v$ with this white $\displaystyle K_{a-1}$ forms a white $\displaystyle K_a$.
Cases 2) and 3) are treated analogously, we always find a white subgraph $\displaystyle K_a$ or a red subgraph $\displaystyle K_b$ or a blue subgraph $\displaystyle K_c$ of the graph $\displaystyle K_n$. This means that we've proved that $\displaystyle r(a,b,c) \leq n$.
(iii) You surely heard of $\displaystyle r(3,3) = 6$, so now when we know (i) and (ii) it is easy to proove (iii). Can you finish it?
Spoiler: