1. ## graph proofs

(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$

2. Originally Posted by wik_chick88
(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$
We do not know that notation.
Anytime you post a question be sure that you define the uncommon terms.

3. 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}$.

4. 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:

wait for it...
Spoiler:

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

$\displaystyle 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$