stylistic:tone, structural:scholar_edition
2-colour case

The theorem for the 2-colour case can be proved by induction on r + s. It is clear from the definition that for all n, R (n, 2) = R (2, n) = n. This starts the induction. We prove that R (r, s) exists by finding an explicit bound for it. By the inductive hypothesis R (r − 1, s) and R (r, s − 1) exist.

Proof. Consider a complete graph on R (r − 1, s) + R (r, s − 1) vertices whose edges are coloured with two colours. Pick a vertex v from the graph, and partition the remaining vertices into two sets M and N, such that for every vertex w, w is in M if edge (vw) is blue, and w is in N if (vw) is red. Because the graph has R (r − 1, s) + R (r, s − 1) = | M | + | N | + 1 {\displaystyle R(r-1,s)+R(r,s-1)=|M|+|N|+1} vertices, it follows that either | M | ≥ R (r − 1, s) {\displaystyle |M|\geq R(r-1,s)} or | N | ≥ R (r, s − 1). {\displaystyle |N|\geq R(r,s-1).} In the former case, if M has a red K then so does the original graph and we are finished. Otherwise M has a blue K and so M ∪ { v } {\displaystyle M\cup \{v\}} has a blue K by the definition of 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 R (r − 1, s) and R (r, s − 1) are both even, the induction inequality can be strengthened to:

Proof. Suppose p = R (r − 1, s) and q = R (r, s − 1) are both even. Let t = p + q − 1 and consider a two-coloured graph of t vertices. If d is the degree of the i -th vertex in the blue subgraph, then by the Handshaking lemma, ∑ i = 1 t d i {\displaystyle \textstyle \sum _{i=1}^{t}d_{i}} is even. Given that t is odd, there must be an even d. Assume without loss of generality that d is even, and that M and N are the vertices incident to vertex 1 in the blue and red subgraphs, respectively. Then both | M | = d 1 {\displaystyle |M|=d_{1}} and | N | = t − 1 − d 1 {\displaystyle |N|=t-1-d_{1}} are even. By the Pigeonhole principle, either | M | ≥ p − 1, {\displaystyle |M|\geq p-1,} or | N | ≥ q. {\displaystyle |N|\geq q.} Since | M | {\displaystyle |M|} is even and p – 1 is odd, the first inequality can be strengthened, so either | M | ≥ p {\displaystyle |M|\geq p} or | N | ≥ q. {\displaystyle |N|\geq q.} Suppose | M | ≥ p = R (r − 1, s). {\displaystyle |M|\geq p=R(r-1,s).} Then either the M subgraph has a red K and the proof is complete, or it has a blue K which along with vertex 1 makes a blue K. The case | N | ≥ q = R (r, s − 1) {\displaystyle |N|\geq q=R(r,s-1)} is treated similarly.