Editing Ramsey's theorem (section)

=== 2-colour case ===
The theorem for the 2-colour case can be proved by [[Mathematical induction|induction]] on {{math|''r'' + ''s''}}.<ref>{{cite journal| first1=Norman | last1=Do | title= Party problems and Ramsey theory
| journal= Austr. Math. Soc. Gazette | year=2006 | volume=33 | number=5 | pages=306–312
| url=http://www.austms.org.au/Publ/Gazette/2006/Nov06/Nov06.pdf#page=17
}}</ref> It is clear from the definition that for all {{mvar|n}}, {{math|1=''R''(''n'', 2) = ''R''(2, ''n'') = ''n''}}. This starts the induction. We prove that {{math|''R''(''r'', ''s'')}} exists by finding an explicit bound for it. By the inductive hypothesis {{math|''R''(''r'' − 1, ''s'')}} and {{math|''R''(''r'', ''s'' − 1)}} exist.

:''Lemma 1.'' <math>R(r, s) \leq R(r-1, s) + R(r, s-1).</math>

''Proof.'' Consider a complete graph on {{math|''R''(''r'' − 1, ''s'') + ''R''(''r'', ''s'' − 1)}} vertices whose edges are coloured with two colours. Pick a vertex {{mvar|v}} from the graph, and partition the remaining vertices into two [[Set (mathematics)|sets]] {{mvar|M}} and {{mvar|N}}, such that for every vertex {{mvar|w}}, {{mvar|w}} is in {{mvar|M}} if edge {{math|(''vw'')}} is blue, and {{mvar|w}} is in {{mvar|N}} if {{math|(''vw'')}} is red. Because the graph has <math>R(r-1,s) + R(r,s-1) = |M| + |N| + 1</math> vertices, it follows that either <math>|M| \geq R(r-1, s)</math> or <math>|N| \geq R(r, s-1).</math> In the former case, if {{mvar|M}} has a red {{mvar|K{{sub|s}}}} then so does the original graph and we are finished. Otherwise {{mvar|M}} has a blue {{math|''K''{{sub|''r'' − 1}}}} and so <math>M \cup \{ v \}</math> has a blue {{mvar|K{{sub|r}}}} by the definition of {{mvar|M}}. The latter case is analogous. Thus the claim is true and we have completed the proof for 2 colours.

In this 2-colour case, if {{math|''R''(''r'' − 1, ''s'')}} and {{math|''R''(''r'', ''s'' − 1)}} are both even, the induction inequality can be strengthened to:<ref>{{cite web|url=http://www.cut-the-knot.org/Curriculum/Combinatorics/ThreeOrThree.shtml#inequality2 |title=Party Acquaintances}}</ref>
:<math>R(r,s) \leq R(r-1,s) + R(r,s-1)-1.</math>
''Proof''. Suppose {{math|1=''p'' = ''R''(''r'' − 1, ''s'')}} and {{math|1=''q'' = ''R''(''r'', ''s'' − 1)}} are both even. Let {{math|1=''t'' = ''p'' + ''q'' − 1}} and consider a two-coloured graph of {{mvar|t}} vertices. If {{mvar|d{{sub|i}}}} is the degree of the {{mvar|i}}-th vertex in the blue subgraph, then by the [[Handshaking lemma]], <math>\textstyle \sum_{i=1}^t d_i </math> is even. Given that {{mvar|t}} is odd, there must be an even {{mvar|d{{sub|i}}}}. Assume without loss of generality that {{math|''d''{{sub|1}}}} is even, and that {{mvar|M}} and {{mvar|N}} are the vertices incident to vertex 1 in the blue and red subgraphs, respectively. Then both <math>|M|= d_1</math> and <math>|N|= t-1-d_1</math> are even. By the [[Pigeonhole principle]], either <math>|M| \geq p-1,</math> or <math>|N| \geq q.</math> Since <math>|M|</math> is even and {{math|''p'' – 1}} is odd, the first inequality can be strengthened, so either <math>|M| \geq p</math> or <math>|N| \geq q.</math>  Suppose <math>|M| \geq p = R(r-1, s).</math> Then either the {{mvar|M}} subgraph has a red {{mvar|K{{sub|s}}}} and the proof is complete, or it has a blue {{math|''K''{{sub|''r'' – 1}}}} which along with vertex 1 makes a blue {{mvar|K{{sub|r}}}}. The case <math>|N| \geq q = R(r, s-1)</math> is treated similarly.