Ramsey’s theorem states that, for a sufficiently large complete graph, any coloring of the edges yields a monochromatic clique. Ramsey numbers, written R(r,s), give the minimum number of vertices that a complete graph must contain such that the graph contains either an r-clique of one color or an s-clique of the other color.
We can divide the set E of edges of a graph G into disjoint subsets of edges by using colors; each subset is then composed of edges of a particular color.
For example, we can use two colors, red and blue, to color the edges of
K
6
, the complete graph on 6 vertices. The vertices are labeled 1 through 6, and an edge joining vertices i and j is denoted by i j.
Randomly choose a (non-empty) subset of edges to color red: