(i) prove that
(ii) prove that
(iii) use parts (i) and (ii) to show that
denotes a Ramsey number. It is the least positive integer such that for any graph on vertices:
• either contains a copy of ,
• or else contains a copy of .
Note so we may restate the definition as: is the least positive integer such that if we 2-colour the edges of then either we have a mono-chromatic or a mono-chromatic .
(i) Let G be a complete graph on 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 . If there's no blue edge then whole G is coloured with white and red, so it contains white or red . We conclude that .
On the other hand, let H be a complete graph on vertices. If we colour it with white and red only, it has to contain white or red . So .
(ii) Let and assume the edges of are coloured white, red and blue. Arbitrarily pick one vertex and consider its edges. We have: The number of white edges incident to is greater or equal to OR the number of red edges incident to is greater or equal to OR the number of blue edges incident to is greater or equal to . Can you see why?
So we distinguish three cases:
1) the number of white edges incident to is greater or equal to ,
2) the number of red edges incident to is greater or equal to ,
3) the number of blue edges incident to is greater or equal to .
In case 1) we can choose exactly vertices connected to by a white edge. These chosen vertices induce complete subgraph. This subgraph contains a white or a red or a blue (because it has vertices). In the first case, vertex with this white forms a white .
Cases 2) and 3) are treated analogously, we always find a white subgraph or a red subgraph or a blue subgraph of the graph . This means that we've proved that .
(iii) You surely heard of , so now when we know (i) and (ii) it is easy to proove (iii). Can you finish it?