Example: R(3,3) = 6
In the following example, the formula R(3,3) provides a solution to the question which asks the minimum number of vertices a graph must contain in order to ensure that either (1) at least 3 vertices in the graph are connected or (2) at least 3 vertices in the graph are unconnected. Note that owing to the symmetrical nature of the problem space, R(r,s) results in the same solution as R(s,r). This is not immediately evident in the example R(3,3) since the values of r and s are the same.
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 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 color), 1 × 4 = 4 (four are the same color, one is the other color), or 2 × 3 = 6 (three are the same color, two are the other color) 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 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.
Read more about this topic: Ramsey's Theorem