Problem Statement
Let $f(n,k)$ be minimal such that there is a graph with $n$ vertices and $f(n,k)$ edges where every set of $k+2$ vertices induces a subgraph with maximum degree at least $k$. Determine $f(n,k)$.
Categories:
Graph Theory
Progress
See also the entry in the graphs problem collection.Source: erdosproblems.com/614 | Last verified: January 15, 2026