1.8.1 Classical Ramsey Numbers An innocent looking problem often gives no hint as to its true nature. Paul Erds [92] A 2-coloring of the edges of a graph G is any assignment of one of two colors to each of the edges of G. Figure 1.120 shows a 2-coloring of the edges of K, using red (thick) and blue (thin). Let p and q be positive integers. The (classical) Ramsey number associated with these integers, denoted by R(p, q), is defined to be the smallest integer n such that every 2-coloring of the edges of Kn either contains a red K, or a blue K, as a subgraph. If 2