1. ## graph proofs

(i) prove that $r(a, b, 2) = r(a, b)$
(ii) prove that $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 $r(3, 3, 3) \leq 17$

2. Originally Posted by wik_chick88
(i) prove that $r(a, b, 2) = r(a, b)$
(ii) prove that $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 $r(3, 3, 3) \leq 17$
We do not know that notation.
Anytime you post a question be sure that you define the uncommon terms.

3. sorry...

$r(m, n)$ denotes a Ramsey number. It is the least positive integer $p$ such that for any graph $G$ on $p$ vertices:

• either $G$ contains a copy of $K_{m}$,
• or else $\overline{G}$ contains a copy of $K_{n}$.

Note $G \cup \overline{G} = K_{p}$ so we may restate the definition as: $r(m, n)$ is the least positive integer $p$ such that if we 2-colour the edges of $K_{p}$ then either we have a mono-chromatic $K_{m}$ or a mono-chromatic $K_{n}$.

4. Hi there
(i) Let G be a complete graph on $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 $K_2$. If there's no blue edge then whole G is coloured with white and red, so it contains white $K_a$ or red $K_b$. We conclude that $r(a,b,2) \leq r(a,b)$.
On the other hand, let H be a complete graph on $r(a,b,2)$ vertices. If we colour it with white and red only, it has to contain white $K_a$ or red $K_b$. So $r(a,b) \leq r(a,b,2)$.

(ii) Let $n = r(a-1,b,c) + r(a,b-1,c) + r(a,b,c-1) - 1$ and assume the edges of $K_n$ are coloured white, red and blue. Arbitrarily pick one vertex $v$ and consider its $n-1$ edges. We have: The number of white edges incident to $v$ is greater or equal to $r(a-1,b,c)$ OR the number of red edges incident to $v$ is greater or equal to $r(a,b-1,c)$ OR the number of blue edges incident to $v$ is greater or equal to $r(a,b,c-1)$. Can you see why?
Spoiler:

wait for it...
Spoiler:

The reason is that otherwise we'd have: The number of white edges incident to $v$ is less or equal to $r(a-1,b,c)-1$ AND the number of red edges incident to $v$ is less or equal to $r(a,b-1,c)-1$ AND the number of blue edges incident to $v$ is less or equal to $r(a,b,c-1)-1$. Which would imply: $n-1 =$ (the number of white edges incident to $v$) + (the number of red edges incident to $v$) + (the number of blue edges incident to $v$) $\leq$
$\leq r(a-1,b,c)-1 + r(a,b-1,c)-1 + r(a,b,c-1)-1 = n-2$, a contradiction.

So we distinguish three cases:

1) the number of white edges incident to $v$ is greater or equal to $r(a-1,b,c)$,
2) the number of red edges incident to $v$ is greater or equal to $r(a,b-1,c)$,
3) the number of blue edges incident to $v$ is greater or equal to $r(a,b,c-1)$.

In case 1) we can choose exactly $r(a-1,b,c)$ vertices connected to $v$ by a white edge. These chosen vertices induce complete subgraph. This subgraph contains a white $K_{a-1}$ or a red $K_b$ or a blue $K_c$ (because it has $r(a-1,b,c)$ vertices). In the first case, vertex $v$ with this white $K_{a-1}$ forms a white $K_a$.

Cases 2) and 3) are treated analogously, we always find a white subgraph $K_a$ or a red subgraph $K_b$ or a blue subgraph $K_c$ of the graph $K_n$. This means that we've proved that $r(a,b,c) \leq n$.

(iii) You surely heard of $r(3,3) = 6$, so now when we know (i) and (ii) it is easy to proove (iii). Can you finish it?
Spoiler:

$r(3,3,3) \leq r(2,3,3)+r(3,2,3)+r(3,3,2)-1 = r(3,3)+r(3,3)+r(3,3)-1 = 17$