Suppose the edges of a complete graph on 6 vertices are coloured red and blue.Pick a vertex,v.There are 5 edges incident to v and so(by the pigeonhole principle)at least 3 of them must be the same colour. Without loss of generality we can assume at least 3 of these edges, connecting the vertex,v,to vertices,r,s and t,are blue.(If not, exchange red and blue in what follows.)If any of the edges,(r,s),(r,() (s,()are also blue then we have an entirely blue triangle.If not,then those three edges are all red and we have an entirely red triangle.Since this argument works for any colouring,any Ke contains a monochromatic K3,and therefore R(3,3)s 6.The popular version of this is called the theorem on friends and strangers. A2-6 An altemative proof works by double counting.It goes as follows: Count the number of ordered triples of vertices,x,y,z,such that the edge,(xy),is red and the edge,(yz),is blue.Firstly,any given vertex will be the middle of either 0x 5=0(all edges from the vertex are the same colour),1 x 4=4(four are the same colour,one is the other colour),or 2 x 3=6(three are the same colour,two are the other colour)such triples.Therefore,there are at most 6x 6=36 such triples.Secondly,for any non-monochromatic triangle (xyz),there exist precisely two such triples.Therefore,there are at most 18 non-monochromatic triangles. Therefore,at least 2 of the 20 triangles in the K6 are monochromatic. Conversely,it is possible to 2-colour a Ks without creating any monochromatic K3.showing that R(3,3)>5. The uniquel21 colouring is shown to the right.Thus R(3,3)=6. The task of proving that R(3,3)s6 was one of the problems of William Lowell Putnam Mathematical Competition in 1953,as well as in the Hungarian Math Olympiad in 1947. Proof of the theorem 2-colour case The theorem for the 2-colour case,can be proved by induction on r+s.3]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. Lemma1.Rr,s）≤R(r-1,s+R(r,s-1) of(1+R(-1)vertice whose edges ed with N.suc w lours.Pick a ver R(revery ve .wi s in Mif ap"w is blu W) th )+R(r, and w rIM≥ R(r e grapl M≥R(, -1).In the former case,if M a red Ks then s does the original graph nd we are finished Otherwise M has a blue Kr-1 and so M U {v)has a blue Kr 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-colocase if R(r,s)and R(r,s-1)are both even,the induction inequality can be strengthened to: R(r,s)s R(r-1,s)+R(r,s-1)-1. A 2-edge-labeling of K5 with no monochromatic K3 Suppose the edges of a complete graph on 6 vertices are coloured red and blue. Pick a vertex, v. There are 5 edges incident to v and so (by the pigeonhole principle) at least 3 of them must be the same colour. Without loss of generality we can assume at least 3 of these edges, connecting the vertex, v, to vertices, r, s and t, are blue. (If not, exchange red and blue in what follows.) If any of the edges, (r, s), (r, t), (s, t), are also blue then we have an entirely blue triangle. If not, then those three edges are all red and we have an entirely red triangle. Since this argument works for any colouring, any K6 contains a monochromatic K3 , and therefore R(3, 3) ≤ 6. The popular version of this is called the theorem on friends and strangers. An alternative proof works by double counting. It goes as follows: Count the number of ordered triples of vertices, x, y, z, such that the edge, (xy), is red and the edge, (yz), is blue. Firstly, any given vertex will be the middle of either 0 × 5 = 0 (all edges from the vertex are the same colour), 1 × 4 = 4 (four are the same colour, one is the other colour), or 2 × 3 = 6 (three are the same colour, two are the other colour) such triples. Therefore, there are at most 6 × 6 = 36 such triples. Secondly, for any non-monochromatic triangle (xyz), there exist precisely two such triples. Therefore, there are at most 18 non-monochromatic triangles. Therefore, at least 2 of the 20 triangles in the K6 are monochromatic. Conversely, it is possible to 2-colour a K5 without creating any monochromatic K3 , showing that R(3, 3) > 5. The unique[2] colouring is shown to the right. Thus R(3, 3) = 6. The task of proving that R(3, 3) ≤ 6 was one of the problems of William Lowell Putnam Mathematical Competition in 1953, as well as in the Hungarian Math Olympiad in 1947. The theorem for the 2-colour case, can be proved by induction on r + s. [3] 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. Lemma 1. R(r, s) ≤ R(r − 1, s) + R(r, s − 1): 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 (v, w) is blue, and w is in N if (v, w) is red. Because the graph has R(r − 1, s) + R(r, s − 1) = |M| + |N| + 1 vertices, it follows that either |M| ≥ R(r − 1, s) or |N| ≥ R(r, s − 1). In the former case, if M has a red Ks then so does the original graph and we are finished. Otherwise M has a blue Kr−1 and so M ∪ {v} has a blue Kr 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:[4] R(r, s) ≤ R(r − 1, s) + R(r, s − 1) − 1. Proof of the theorem 2-colour case