The Construction of Certain Graphs

Abstract

A graph G is called complete if any two of its vertices are connected by an edge; a set of vertices of G are said to be independent if no two of them are connected by an edge. It follows from a well-known theorem of Ramsay (1) that for each pair of positive integers k, l there is an integer f(k , l), which we take to be minimal, such that every graph with f(k, l) vertices either contains a complete graph of k vertices or a set of l independent points.