graph proofs

**wik_chick88** · August 30th 2009, 10:23 PM

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

**Plato** · August 31st 2009, 03:12 AM

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.

**wik_chick88** · September 2nd 2009, 08:36 PM

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

**Taluivren** · September 3rd 2009, 07:52 AM

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:

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:

Thread: graph proofs

LinkBack

Thread Tools

Display

graph proofs

Similar Math Help Forum Discussions

Graph Theory: Relationship between maximum degree of a graph and maximal matching

Graph connectivity proofs

Graph Proofs- Isomorphic

proofs in graph theory...I don't understand how to prove this

Sequence Convergence Proofs vs. Continuity Function Proofs

Search Tags