Complementing a local maximum-degree condition

../

---

In Problem 614, let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph $G$ such that each set of $k+2$ vertices contains a vertex of degree at least $k$ in its induced subgraph. Fix $k\ge1$ and $n\ge k+2$. Let $\mathcal F_{k+2}$ be the finite family of all simple graphs on exactly $k+2$ vertices with minimum degree at least $2$. Then

$$f(n,k)=\binom n2-\operatorname{ex}(n,\mathcal F_{k+2}). \tag{1}$$

Here avoiding a family means containing none of its members as an ordinary, not necessarily induced, subgraph. This elementary reformulation and the specializations below are author-recorded by Plasma AI, without independent review. They do not evaluate the extremal function for general $k$.

Put $H=\overline G$. For a set $S$ of $k+2$ vertices and $v\in S$,

$$d_{G[S]}(v)+d_{H[S]}(v)=k+1.$$

Thus $G[S]$ has a vertex of degree at least $k$ exactly when $H[S]$ has a vertex of degree at most $1$. Failure means that $H[S]$ itself belongs to $\mathcal F_{k+2}$. Conversely, if $H$ contains any member of that family as a subgraph, the induced graph on its vertices still has minimum degree at least $2$, so $G$ fails the condition there. Complementation is a bijection, and minimizing $e(G)=\binom n2-e(H)$ proves (1).

For $k=1$ the only family member is $K_3$, so Mantel's theorem gives

$$f(n,1)=\binom n2-\left\lfloor\frac{n^2}{4}\right\rfloor.$$

For $k=2$, every four-vertex graph of minimum degree at least $2$ contains a $C_4$. If it is triangle-free, the two neighbors of any vertex are nonadjacent and both must be adjacent to the fourth vertex, giving a four-cycle. If it has a triangle, the fourth vertex has two neighbors in that triangle; together with its third vertex they give a four-cycle. Since $C_4$ itself has minimum degree $2$, avoiding $\mathcal F_4$ is exactly avoiding $C_4$. Hence

$$f(n,2)=\binom n2-\operatorname{ex}(n,C_4).$$

The latter identity embeds the exact four-cycle extremal problem in the local-degree question. An asymptotic estimate of $\operatorname{ex}(n,C_4)$ would supply an asymptotic estimate here, not every exact value. For larger $k$, a list of forbidden graphs at fixed $k$ is finite while the host order $n$ is still unbounded. A computation at selected $(n,k)$ does not extend without a separate structural argument.