Given integers $k$ and $n$ with $2 \le k < n$, how does one construct a graph on $n$ vertices that contains no $k$-clique and has the maximal number of edges?
This sounds like basic combinatorics, but I don't know where to find the result. Pointers would be welcome if this is well-known.
Ideally I would like a deterministic procedure to construct such a maximal graph in $n^{O(1)}$ time.
One graph with $n$ vertices that is guaranteed not to contain $K_k$ is $\overline{K_{n-k+2} + \overline{K_{k-2}}}$, the complement of the graph formed by the disjoint union of $K_{n-k+2}$ and $k-2$ isolated vertices. Whenever one picks $k$ vertices from it, at least two of these must be from the subset which is completely disconnected, so they cannot form a clique. This can clearly be constructed in polynomial time, and is quite dense for $k$ close to $n$. However, this construction yields rather sparse graphs when $k$ is small relative to $n$, so it seems unlikely to be the optimal construction.
