Extremal Graph Theory

A complete multipartite graph contains every vertex pair except pairs within one part. If its part sizes are $n_1,\dots ,n_r$, its edge count is $\left(\genfrac{}{}{0px}{}{n}{2}\right)-{\sum }_i\left(\genfrac{}{}{0px}{}{n_i}{2}\right)=\frac{1}{2}(n^2-{\sum }_i{n}_i^2)$. Substituting the $a$ sizes $q+1$ and the remaining sizes $q$ gives both displayed exact formulas.

If $n_i\ge n_j+2$, moving one vertex from part $i$ to part $j$ changes ${\sum }_k{n}_k^2$ by $(n_i-1{)}^2+(n_j+1{)}^2-n_i^2-n_j^2=-2(n_i-n_j-1)<0$, so it strictly increases the edge count. Repetition ends exactly when every two part sizes differ by at most $1$, which forces the quotient-remainder sizes and proves both maximality and uniqueness.

The identity ${\sum }_i(n_i-n\mathrm{/}r{)}^2={\sum }_i{n}_i^2-n^2\mathrm{/}r\ge 0$ gives $e\le (r-1)n^2\mathrm{/}(2r)$. Equality requires every $n_i=n\mathrm{/}r$, possible exactly when $r$ divides $n$; for the balanced integer sizes the converse is immediate.

Steps 1.1-2.2 prove the exact count, balancing characterization, quadratic bound, and both equality cases, including $n=0$ and $r=1$.

The assertion is immediate for $n=0,1,2$. Assume it, including uniqueness, for $n-2$, and let $G$ be a triangle-free $n$-vertex graph. If $G$ has no edge its bound is immediate. Otherwise choose an edge $uv$. No vertex other than $u,v$ is adjacent to both ends, so $d(u)+d(v)\le n$.

Delete $u,v$ to obtain a triangle-free graph $G^{\mathrm{\prime }}$. The removed edges number $d(u)+d(v)-1$, so $e(G)\le \lfloor (n-2{)}^2\mathrm{/}4\rfloor +n-1=\lfloor n^2\mathrm{/}4\rfloor$. The graph $T_{n,2}$ is triangle-free and has the last edge count, proving the exact maximum.

Suppose equality holds. Then $G^{\mathrm{\prime }}\cong T_{n-2,2}$, $d(u)+d(v)=n$, and every other vertex is adjacent to exactly one of $u,v$. In each part of $G^{\mathrm{\prime }}$, triangle-freeness forces all vertices to choose the same endpoint: two vertices in opposite parts choosing the same endpoint would form a triangle with their cross edge. Hence adjoining $u$ to one part and $v$ to the other makes $G$ complete bipartite.

Its two part sizes sum to $n$ and its product is $\lfloor n^2\mathrm{/}4\rfloor$; the balancing equality in the preceding lemma forces them to differ by at most $1$. Thus $G\cong T_{n,2}$. Conversely that graph has equality, completing the induction and the uniqueness proof.

Steps 1.1-4.1 prove Mantel's theorem independently of Turán's theorem, for all $n$ and with equality fully characterized.

Replacing $u$ by a twin of a nonneighbor $v$ creates no $K_{r+1}$: any new clique containing $u$ becomes a clique after replacing $u$ by $v$. Its edge-count change is $d(v)-d(u)$. Since $G$ is extremal, nonadjacent vertices must have equal degrees, or duplicating the higher-degree one would increase the edge count. Thus every such replacement preserves extremality.

Group vertices with equal open neighbourhoods into twin classes. If two nonadjacent vertices lie in different classes, duplicate every vertex of the smaller class into the larger class. Step 1.1 preserves the edge count, while the sum of the squares of twin-class sizes strictly increases. This integer is at most $n^2$, so finitely many repetitions reach a graph in which nonadjacent vertices have equal neighbourhoods.

In the final graph, nonadjacency is transitive: if $u$ is nonadjacent to $v$ and $v$ to $w$, then $N(u)=N(v)=N(w)$, so $u$ is nonadjacent to $w$. Its equivalence classes are independent sets, and every pair of distinct classes is completely joined. The graph is therefore complete multipartite. Choosing one vertex from each nonempty part gives a clique, so the number of parts is at most $r$.

Steps 1.1-3.1 give a terminating, edge-preserving symmetrisation from the extremal graph to the asserted complete multipartite graph.

The graph $T_{n,r}$ is $K_{r+1}$-free. Zykov symmetrisation sends an extremal graph to a complete $k$-partite graph with $k\le r$ and the same edge count; adding empty parts makes it complete $r$-partite, so balancing bounds its edges by $e(T_{n,r})$. Hence the displayed extremal number is exact.

For uniqueness, induct on $r$. At $r=1$, a $K_2$-free graph is edgeless and equals $T_{n,1}$. The case $n=0$ is also immediate. Assume $r\ge 2$, $n\ge 1$, and rigidity for $r-1$, and let $G$ attain $e(T_{n,r})$. Choose a vertex $v$ of maximum degree $d$, put $A=N(v)$ and $B=V(G)\setminus A$. Then $G[A]$ is $K_r$-free and $e(G)\le e(G[A])+{\sum }_{b\in B}d(b)\le e(T_{d,r-1})+(n-d)d$. The last expression is the edge count of a complete $r$-partite graph whose one part has size $n-d$ and whose remaining parts are balanced on $d$ vertices, so balancing makes it at most $e(T_{n,r})$.

Equality for $G$ forces equality throughout step 1.2. The first inequality forces $G[B]$ to have no edge, the degree inequality forces every $b\in B$ to have degree $d$, and $\mathrm{\mid }A\mathrm{\mid }=d$ then forces every vertex of $B$ to be adjacent to every vertex of $A$. Inductive rigidity gives $G[A]\cong T_{d,r-1}$, and balancing equality makes the resulting $r$ part sizes differ by at most $1$. Thus $G\cong T_{n,r}$.

Conversely $T_{n,r}$ is $K_{r+1}$-free and has the extremal edge count by step 1.1. The induction therefore proves both directions of the equality characterization.

Steps 1.1-3.1 prove the exact formula and uniqueness for every $n$, including $n<r$ and $n=0$.

Partition $(s-1)(t-1)$ vertices into $s-1$ parts of size $t-1$. Colour every edge within a part blue and every edge between parts red. A red clique uses at most one vertex from each part, so has size at most $s-1$; a blue clique lies in one part, so has size at most $t-1$.

Thus this colouring has neither a red $K_s$ nor a blue $K_t$. The Ramsey-number definition makes $R(s,t)$ strictly larger than $(s-1)(t-1)$, proving the integer lower bound.

Let $G$ be an $n$-vertex $H$-free graph with $e(G)=\mathrm{ex}(n,H)$. Every induced graph $G-v$ is still $H$-free, so $e(G-v)\le \mathrm{ex}(n-1,H)$.

Count pairs $(e,v)$ with $e\in E(G)$ and $v$ not incident with $e$. Each edge has $n-2$ choices of $v$, while for fixed $v$ there are $e(G-v)$ choices. Double counting gives $(n-2)e(G)={\sum }_{v}e(G-v)\le n\mathrm{ex}(n-1,H)$.

Substituting $e(G)=\mathrm{ex}(n,H)$ and using $\left(\genfrac{}{}{0px}{}{n}{2}\right)=n(n-1)\mathrm{/}2$ and $\left(\genfrac{}{}{0px}{}{n-1}{2}\right)=(n-1)(n-2)\mathrm{/}2$ turns step 2.1 into the displayed inequality. There is no comparison before $n=3$, so the sequence begins at $n=2$.

The normalized extremal numbers are nonincreasing. They lie in $[0,1]$ because an edge count is nonnegative and no simple $n$-vertex graph has more than $\left(\genfrac{}{}{0px}{}{n}{2}\right)$ edges.

Bounded monotone convergence makes the sequence converge to its infimum. The bounds in step 1.1 place that value in $[0,1]$.

If $\pi (H)+\epsilon >1$, take $\delta =1$ and $N=2$: for $n\ge 2$ one has $\left(\genfrac{}{}{0px}{}{n}{2}\right)\ge 1$, so $(\pi (H)+\epsilon )\left(\genfrac{}{}{0px}{}{n}{2}\right)>\left(\genfrac{}{}{0px}{}{n}{2}\right)\ge e(G)$ and no graph satisfies the edge hypothesis. The threshold cannot be lowered to $1$, because $\left(\genfrac{}{}{0px}{}{1}{2}\right)=0$ makes the hypothesis vacuous at $n=1$ while the conclusion there demands $\delta n^h=1$ embedding of an $h$-vertex $H$ into a one-vertex graph. Hence assume $\pi (H)+\epsilon \le 1$, and choose $m\ge \max (h,2)$ with $\mathrm{ex}(m,H)\mathrm{/}\left(\genfrac{}{}{0px}{}{m}{2}\right)<\pi (H)+\epsilon \mathrm{/}2$. For an $n$-vertex $G$ satisfying the hypothesis, the average edge density of its induced $m$-vertex subgraphs equals $e(G)\mathrm{/}\left(\genfrac{}{}{0px}{}{n}{2}\right)\ge \pi (H)+\epsilon$: each edge lies in $\left(\genfrac{}{}{0px}{}{n-2}{m-2}\right)$ such subsets.

Let $p$ be the fraction of $m$-subsets inducing more than $\mathrm{ex}(m,H)$ edges. The remaining subsets have density below $\pi (H)+\epsilon \mathrm{/}2$, while every density is at most $1$. Therefore $\pi (H)+\epsilon \le (1-p)(\pi (H)+\epsilon \mathrm{/}2)+p$, so $p\ge \epsilon \mathrm{/}2$ after weakening the resulting positive lower bound if necessary. Each good subset induces an $m$-vertex graph with more than $\mathrm{ex}(m,H)$ edges, so by [F4] it is not $H$-free: it admits an injective ordinary-subgraph embedding of $H$.

Count pairs consisting of a good $m$-set and a chosen injective copy of $H$ inside it. There are at least $(\epsilon \mathrm{/}2)\left(\genfrac{}{}{0px}{}{n}{m}\right)$ pairs after choosing one copy in each good set, while any fixed embedding lies in $\left(\genfrac{}{}{0px}{}{n-h}{m-h}\right)$ $m$-sets. Thus the number of embeddings is at least $(\epsilon \mathrm{/}2)\left(\genfrac{}{}{0px}{}{n}{m}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{n-h}{m-h}\right)=(\epsilon \mathrm{/}2)\left(\genfrac{}{}{0px}{}{n}{h}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{m}{h}\right)$. For $n\ge 2h$, this is at least $\delta n^h$ for some $\delta >0$ depending only on $H,\epsilon$.

Taking $N\ge \max (m,2h)$ completes the assertion with the constants constructed above.

Count pairs $(S,b)$ with $S\subseteq A$, $\mathrm{\mid }S\mathrm{\mid }=s$, and $S\subseteq N(b)$. Counting first by $b$ gives the left side. For fixed $S$, at most $t-1$ vertices of $B$ contain $S$ in their neighbourhood, or those vertices with $S$ form the forbidden $K_{s,t}$. Counting first by $S$ proves the upper bound.

Partitioning the $s$-subsets of a $d$-element set according to whether they contain one distinguished element gives $\left(\genfrac{}{}{0px}{}{d}{s}\right)-\left(\genfrac{}{}{0px}{}{d-1}{s}\right)=\left(\genfrac{}{}{0px}{}{d-1}{s-1}\right)$, a nondecreasing function of $d$. Thus if $d_i\ge d_j+2$, replacing $(d_i,d_j)$ by $(d_i-1,d_j+1)$ does not increase the binomial sum. Repetition terminates at values $q=\lfloor E\mathrm{/}n\rfloor$ and $q+1$.

For integers $d\ge s-1$, $\left(\genfrac{}{}{0px}{}{d}{s}\right)\ge (d-s+1{)}^s\mathrm{/}s!$. Writing $E\mathrm{/}n=q+\theta$ with $0\le \theta <1$, the balanced sum is the corresponding linear interpolation between $\left(\genfrac{}{}{0px}{}{q}{s}\right)$ and $\left(\genfrac{}{}{0px}{}{q+1}{s}\right)$; convexity of $y\mapsto y^s$ on nonnegative reals bounds it below by $n(E\mathrm{/}n-s+1{)}^s\mathrm{/}s!$.

Steps 1.1-2.1 prove the common-neighbour upper count and the discrete smoothing lower count with the stated threshold.

Let $E=e(G)$ in the bipartite problem. If $m=0$ or $n=0$, then $E=0$ and the first bound is immediate. Assume $m,n\ge 1$. If $E\mathrm{/}n<s-1$, the bound is again immediate. Otherwise the preceding lemma gives $n(E\mathrm{/}n-s+1{)}^s\mathrm{/}s!\le (t-1)\left(\genfrac{}{}{0px}{}{m}{s}\right)\le (t-1)m^s\mathrm{/}s!$. Taking nonnegative $s$th roots and rearranging yields $E\le (t-1{)}^{1\mathrm{/}s}m{n}^{1-1\mathrm{/}s}+(s-1)n$.

For an ordinary $K_{s,t}$-free graph on $N$ vertices, form a bipartite incidence graph between two copies of its vertex set, joining the left copy of $u$ to the right copy of $v$ exactly when $uv$ is an edge. It is oriented-$K_{s,t}$-free and has $2e(G)$ edges. Apply step 1.1 with $m=n=N$ and divide by $2$.

The displayed ordinary bound is $O_{s,t}(N^{2-1\mathrm{/}s})$, since its linear term has no larger order. At $s=1$, step 1.1 uses the same algebra and gives the stated exact specialization.

Choose a bipartition of $H$ and enlarge its two sides, including any isolated vertices, to positive sizes $s,t$ such that $H$ is an ordinary subgraph of $K_{s,t}$. Every $H$-free graph is then $K_{s,t}$-free.

Hence $0\le \mathrm{ex}(n,H)\le \mathrm{ex}(n,K_{s,t})=O_{s,t}(n^{2-1\mathrm{/}s})$. Dividing by $\left(\genfrac{}{}{0px}{}{n}{2}\right)$ makes the right side tend to $0$. The existing limit $\pi (H)$ is therefore $0$.

The at-least-one-edge hypothesis ensures both bipartition sides can be chosen positive and is exactly the scope in which the extremal density was defined.