= Solution
The <Erdős-Stone theorem> says that, for a fixed <graph> $F$ with <chromatic number> $q\ge2$,
$$
\boxed{\operatorname{ex}(n,F)=\left(1-\frac1{q-1}+o(1)\right)\binom n2.}
$$
The lower bound comes from the balanced <Turán graph> with $q-1$ parts; the theorem supplies the matching asymptotic upper bound. Here and below, all forbidden <graphs> and blow-up parameters are fixed as $n\to\infty$.
\b[First obtain an almost spanning, almost complete multipartite core.] Put $\alpha_r=1-1/r$. We give the stability argument, rather than infer pointwise degree bounds by differentiating an asymptotic edge-count formula. Suppose first $r\ge2$.
We need two elementary ingredients. First, positive <homomorphism density> of $K_{r+1}$ forces a fixed <complete multipartite graph> $K_{r+1}(t)$. To see this, perform <vertex cloning in a graph>, replacing one vertex by $t$ independent twins. Conditional on the images of the other vertices, its contribution to the <homomorphism density> changes from a number $p$ to $p^t$; <Jensen inequality> gives $\mathbb E p^t\ge(\mathbb E p)^t$. Duplicating each original vertex therefore gives
$$
t(K_{r+1}(t),G)\ge t(K_{r+1},G)^{\,t^{r+1}}.
$$
A positive lower bound on the right supplies a positive proportion of all maps of the blow-up. Only $O(n^{(r+1)t-1})$ maps fail to be injective, so for large $n$ at least one map is an embedding. Consequently a $K_{r+1}(t)$-free sequence has $o(n^{r+1})$ copies of $K_{r+1}$. The <clique removal lemma>, proved in the next solution, then deletes $o(n^2)$ edges to give a $K_{r+1}$-free <graph> $J_n$ with $e(J_n)=\alpha_r n^2/2-o(n^2)$.
Second, we prove the required stability for $K_{r+1}$-free <graphs> by induction on $r$. For $r=1$ such a <graph> is edgeless. In an $m$-vertex $K_{r+1}$-free <graph> $J$, take a vertex of maximum <vertex degree> $D$, put $A=N(v)$ and $B=V(J)\setminus A$, and note that $J[A]$ is $K_r$-free. The <Turan theorem> and the maximum-degree bound give
$$
\begin{aligned}
e(J)&=e(J[A])+\sum_{u\in B}d(u)-e(J[B])\\
&\le\frac{r-2}{2(r-1)}D^2+(m-D)D-e(J[B])\\
&=\frac{r-1}{2r}m^2-\frac{r}{2(r-1)}\left(D-\frac{r-1}{r}m\right)^2-e(J[B]).
\end{aligned}
$$
If $e(J)=\alpha_r m^2/2-o(m^2)$, both nonnegative error terms are $o(m^2)$: $D=\alpha_r m+o(m)$ and $e(J[B])=o(m^2)$. The deficit in the bound for $e(J[A])$ is likewise $o(m^2)$. Induction partitions $A$ into $r-1$ classes with a total of $o(m^2)$ internal edges; adjoining $B$ gives an $r$-class partition with the same property. Applying this to $J_n$ and restoring the removed edges gives such a partition $V_1,\ldots,V_r$ of $G_n$.
The number of possible crossing edges is $\tfrac12(n^2-\sum_i|V_i|^2)\le\alpha_r n^2/2$. Since the actual crossing-edge count is within $o(n^2)$ of this maximum, $|V_i|=n/r+o(n)$ for every $i$, and there are $o(n^2)$ missing crossing edges. Choose $a_n\to0$ so slowly that the number of vertices missing more than $a_n n$ neighbours in other classes is $o(n)$. Delete those vertices and all internal edges. The remaining <r-partite graph> $Q_n$ has $n-o(n)$ vertices and every vertex has crossing <vertex degree> at least $\alpha_r n-o(n)$. The <Turan theorem>, or the size of a largest part, supplies the matching upper bound for its minimum <vertex degree>. Thus
$$
\boxed{\delta(Q_n)=\left(1-\frac1r+o(1)\right)n.}
$$
This is a <high-minimum-degree multipartite stability subgraph>. The subgraph need not be spanning; deleting the exceptional $o(n)$ vertices is essential. For $r=1$, the spanning edgeless subgraph already proves the assertion.
\b[Extremality forces the minimum degree.] Choose $t\ge|V(F)|$. A proper $(r+1)$-<graph colouring> embeds $F$ in $K_{r+1}(t)$, so every $F$-free $H_n$ is also $K_{r+1}(t)$-free. By the <Erdős-Stone theorem>, its extremal edge count has the needed asymptotic size. The preceding proof supplies core classes $W_1,\ldots,W_r$ of size $n/r+o(n)$ in which every vertex misses only $o(n)$ crossing neighbours, uniformly over the core.
Delete an arbitrary vertex $x$ from $H_n$ and introduce a new vertex $z$ adjacent precisely to $W_2\cup\cdots\cup W_r$ with $x$ removed if necessary. The new <graph> is still $F$-free. Indeed any new copy would use $z$, all its neighbours in that copy would be in the specified core classes, and their set of <common neighbours> in $W_1$ has size $n/r-o(n)$. A vertex of this common neighbourhood outside the bounded vertex set of the copy replaces $z$, producing an existing copy of $F$ in $H_n$, a contradiction. For $r=1$ the new vertex is isolated and the same conclusion is immediate.
The replacement adds $\alpha_r n-o(n)$ edges. Since $H_n$ has the maximum possible number of edges, $d_{H_n}(x)\ge\alpha_r n-o(n)$. As $x$ was arbitrary and the minimum <vertex degree> is at most the average <vertex degree>,
$$
\boxed{\delta(H_n)=\left(1-\frac1r+o(1)\right)n.}
$$
This proves the <minimum degree of an extremal forbidden-subgraph graph>. The replacement argument avoids the invalid implication $\operatorname{ex}(n,F)-\operatorname{ex}(n-1,F)=\alpha_r n+o(n)$ based solely on the asymptotic formula.
\b[A <colour-critical vertex> also bounds the maximum degree.] Suppose a vertex $x$ of $H_n$ has $d(x)\ge\alpha_r n+\varepsilon n$ for some fixed $\varepsilon>0$. Since the core omits only $o(n)$ vertices and all its classes have size $n/r+o(n)$, $x$ has at least $\varepsilon n-o(n)$ neighbours in each $W_i$. Otherwise, even counting every vertex in all other classes and outside the core would give too small a <vertex degree>.
Inside these $r$ neighbourhood sets, greedily choose a fixed number $t\ge|V(F)|$ of vertices in each class. Every previously chosen vertex excludes only $o(n)$ crossing nonneighbours, so each next candidate set still has positive linear size. This produces $K_r(t)$ inside $N(x)$. A proper $r$-<graph colouring> of $F-v$ embeds it in that <complete multipartite graph>; map $v$ to $x$. All required incident edges exist, so this embeds $F$, a contradiction. The case $r=1$ simply uses enough neighbours to embed the edgeless $F-v$. Hence $\Delta(H_n)\le\alpha_r n+o(n)$, and the average-degree lower bound completes the answer:
$$
\boxed{\Delta(H_n)=\left(1-\frac1r+o(1)\right)n.}
$$
Back to article page
