if we color the edges of the complete graph K6 on six vertices using two colors, then there will always be a monochromatic triangle; a cycle of length 3 whose edges are all red or all blue.

1. Show that this result is tight by drawing an edge colouring of the graph K5 using two colours that has no monochromatic K3. Just to be clear, you should make a drawing that looks something like this, but that has no monochromatic triangles:

Now let's try to generalize the problem. Let R(s,t) be the minimum integer n such that every 2-colouring of the edges of Kn contains:

• a clique of size s whose edges are all red; or
• a clique of size t whose edges are all blue.

The theorem mentioned above says that R(3,3)6 and your solution to the previous question shows that R(3,3)>5, so R(3,3)=6.

1. Explain, in a few words, why R(s,2)=s for any s2. (This is also the same as saying that R(2,t)=t for any t2.)
2. Now argue that that, for any integers s,t3, R(s,t)R(s1,t)+R(s,t1). (Hint: Start by slowly and carefully repeating the argument used in class and modifying it as necessary.)

Note that these two questions give a proof, by induction, that R(s,t) is finite; for any s,t2, any sufficiently large group of people will contain s mutual friends or t mutual strangers.

1. Show that this result is tight by drawing an edge colouring of the graph K, using two colours that has no monochromatic K3. Just to be clear, you should make a drawing that looks something like this, but that has no monochromatic triangles: Now let's try to generalize the problem. Let R(s, t) be the minimum integer n such that every 2- colouring of the edges of Kn contains: a clique of size s whose edges are all red; or a clique of size t whose edges are all blue. The theorem mentioned above says that R(3, 3) 5, so R(3,3) = 6. 1. Explain, in a few words, why R(s, 2) = s for any s > 2. (This is also the same as saying that R(2, t) = = t for any t > 2.) 2. Now argue that that, for any integers s, t > 3, R(s, t)