An extremal problem in graph theory
P. Erdös, Leo Moser · Journal of the Australian Mathematical Society · 1970
G(n;l) will denote a graph of n vertices and l edges. Let f0(n, k) be the smallest integer such that there is a G (n;f0(n, k)) in which for every set of k vertices there is a vertex joined to each of these. Thus for example fo = 3 since in a triangle each pair of vertices is joined to a third. It can readily be checked that fo = 5 (the extremal graph consists of a complete 4-gon with one edge removed). In general we will prove: Let n > k, and then f0(n, k) = f(n, k).