A problem on sparse induced subgraphs

Problem (proposed by Erdös [1])

Let \(f(n,k)\) denote the smallest integer for which there is a graph with \(n\) vertices and \(f(n,k)\) edges so that every set of \(k+2\) vertices induces a subgraph with maximum degree at least \(k\). Determine \(f(n,k)\).

1 R. Faudree, C. C. Rousseau and R. H. Schelp, Problems in graph theory from Memphis, The Mathematics of Paul Erdös, II (R. L. Graham and J. Nešetril, eds.), 7-26, Springer-Verlag, Berlin, 1996.