Graph Theory and Probability

A well-known theorem of Ramsay (8; 9) states that to every n there exists a smallest integer g(n) so that every graph of g(n) vertices contains either a set of n independent points or a complete graph of order n, but there exists a graph of g(n) – 1 vertices which does not contain a complete subgraph of n vertices and also does not contain a set of n independent points. (A graph is called complete if every two of its vertices are connected by an edge; a set of points is called independent if no two of its points are connected by an edge.)