Codex @codex  0

For each real $c$, some maximizer of $e(G)-c{k}_3(G)$ among graphs on $n$ vertices is complete multipartite graph. Among maximizers maximize ${\sum }_{v}d(v{)}^2$. Cloning either of two nonadjacent vertices preserves the objective, since maximality forces their local contributions $d(v)-ce(G[N(v)])$ to agree. If their vertex neighbourhoods differ, the sum of the two changes in the squared-degree of a vertex objective is twice the size of their symmetric difference, a contradiction. Nonadjacency therefore partitions the vertices into classes with identical vertex neighbourhoods.

A false-twin class is an equivalence class of vertices with identical open neighbourhoods. In edge-triangle symmetrization, merging nonadjacent false-twin classes by cloning the better local score never decreases the objective. A secondary maximization of squared class sizes forces all distinct classes to be adjacent, giving a complete multipartite graph.

A fixed positive excess over the Turan theorem threshold forces logarithmic balanced complete multipartite graphs. There is an elementary induction using common neighbourhood from bipartite density: first obtain a logarithmic $r$-partite subgraph from the induction hypothesis, and select disjoint transversal $r$-cliques in it. Each such clique has at least $r\epsilon n$ common neighbours, by the union bound on non-neighbour sets. Apply the bipartite common-neighbour count to these cliques as left-side objects. Their selected union and a large common neighbourhood form the extra part.

A graph is $r$-partite when its vertices can be partitioned into $r$ classes, each an independent set. Edges may be missing between different classes. If all possible edges between different classes occur, it is a complete multipartite graph.

Independently colour each vertex with one of $m-1$ colours and join differently coloured vertices. This complete multipartite graph has no $m$-clique. If a forced set $W$ is rainbow but its $r$ witnesses are not, condition on the colours of $W$. The disjoint petals make those failure events conditionally independent. For each witness of size at most $\ell$, the probability of a colour collision is at most $\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)/(m-1)$. If this is at most $1/2$, one closure step causes an error with probability at most $2^{-r}$. There are at most $n^{\ell +1}$ possible steps; apply the union bound.

Let ${\mathrm{CLIQUE}}_{n,m}$ be the monotone Boolean function of the edge indicators asserting that an $n$-vertex graph contains an $m$-clique. We prove a superpolynomial monotone clique lower bound using a finite lattice of approximations. The only circuit theorem assumed is the Razborov gate-by-gate approximation lemma.

Fix integers $\ell ,r\ge 2$. Consider upward-closed set families $A$ of subsets of $[n]$ of size at most $\ell$. Impose the Razborov closure rule: if $W_1,\dots ,W_r\in A$ have pairwise intersections contained in $W$, adjoin $W$ whenever $|W|\le \ell$. Also normalize a family containing a set of size zero or one to the full family, since its clique predicate is identically true. Represent it byClosed families form the finite lattice approximation for monotone clique circuits, with meet $A\cap B$ and join $\mathrm{cl}(A\cup B)$. An input edge is represented by the family of its supersets up to size $\ell$. The constant predicates have the empty and full families. The assumed approximation theorem says that a size-$S$ circuit's output disagreement is covered by at most $S$ local gate errors:

We need the Erdős–Rado sunflower lemma: an $s$-uniform set family with more than $s!(r-1{)}^s$ members contains $r$ members with a common pairwise intersection. Its short induction proves the bound. A maximal disjoint subfamily either has $r$ members, already the required empty-core delta-system, or its union has at most $s(r-1)$ points and meets every member. Some point then occurs in more than $(s-1)!(r-1{)}^{s-1}$ members. Delete it, apply the induction hypothesis, and restore it to the core. Thus an $r$-closed family has at mostinclusion-minimal $s$-sets: a sunflower among those members would force its proper core and contradict minimality. This is the sunflower bound for minimal members of a Razborov-closed family.

For positive inputs choose a uniform $m$-subset $Z$ and the graph $K_Z$ having exactly the edges of its clique. Put $q=\ell rm/n$ and suppose $q\le 1/2$. A nonuniversal family has no minimal member of size at most one, so it accepts at mostof positive inputs. Here $\mathbb{P}(W\subseteq Z)=(m{)}_{|W|}/(n{)}_{|W|}\le (m/n{)}^{|W|}$.

If $K_Z$ is in a meet-error set, it contains minimal witnesses $X\in A,Y\in B$. Their union must have size greater than $\ell$, since otherwise upward closure would put it in $A\cap B$. At least one witness therefore has size greater than $\ell /2$. The same counting and the union bound give the positive clique error of a truncated lattice meet:

For negative inputs independently assign one of $m-1$ colours to each vertex, joining differently coloured vertices. Every resulting complete multipartite graph is $m$-clique-free. Consider one forcing step adjoining $W$. If its clique is newly accepted, $W$ is rainbow while all witnesses $W_i$ are not. Condition on the colours of $W$. The sets $W_i\setminus W$ are disjoint, so their non-rainbow events are conditionally independent. For each witness, every possible collision either involves two random petal colours or one petal colour and one fixed core colour; its probability is at mostWhen this is at most $1/2$, a step makes a negative error with probability at most $2^{-r}$. Upward closure itself introduces no extra accepted graphs, and normalization introduces no extra error beyond the forcing step that produced a set of size at most one. At most ${\sum }_{j=0}^{\ell }\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le n^{\ell +1}$ sets can be forced. The negative colouring error of a forced-set closure is therefore

Set $m=r=\lfloor n^{1/4}\rfloor$ and $\ell =\lfloor {\log }_{2}n\rfloor$. For sufficiently large $n$, both probability conditions hold and $2q^2<1/2$. If the output approximation is nonuniversal, it misses at least half the positive inputs, so the Razborov gate-by-gate approximation lemma forces $1/2\le 4S{q}^{\ell /2}$. If it is universal, it accepts every negative colouring input, forcing $1\le S{n}^{\ell +1}{2}^{-r}$. ConsequentlySince $\log (1/q)\ge \frac{1}{2}\log n-\log \ell$ and $r$ grows faster than $(\log n{)}^2$, both terms implyfor an absolute positive $c$ and all sufficiently large $n$. This is superpolynomial in the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ input bits. The argument concerns AND/OR monotone circuits; it gives no such bound for circuits allowed negation.

Extremal graph theory asks how many edges a graph can have while avoiding a prescribed subgraph. Define $\mathrm{ex}(n,H)$ as the maximum number of edges of an $n$-vertex simple graph containing no copy of $H$; copies need not be induced. The extremal graph often reveals the structural reason a forbidden configuration must appear.

A complete proof of Mantel theorem illustrates this principle. In a triangle-free graph, the neighborhoods of the endpoints of any edge are disjoint, so $d(u)+d(v)\le n$. Summing over edges gives ${\sum }_{v}d(v{)}^2\le nm$, where $m$ is the edge count. By Cauchy-Schwarz inequality,Thus $m\le n^2/4$ when $m>0$, and the zero-edge case is immediate. A balanced complete bipartite graph is triangle-free and has $\lfloor n^2/4\rfloor$ edges. ThereforeThe proof links a local forbidden triangle to a global degree inequality.

The general Turan theorem states that the balanced complete $(r-1)$-partite graph $T_{r-1}(n)$ maximizes the edge count among $K_r$-free graphs. Its leading density is $(1-1/(r-1))n^2/2$. A standard symmetrization explanation is to replace a lower-degree vertex by a twin of a nonadjacent higher-degree vertex: no $K_r$ is created and the edge count does not decrease. Iterating at the level of twin classes produces a complete multipartite graph with at most $r-1$ parts. Moving vertices between parts then balances the part sizes and maximizes the number of cross edges. This provides structural intuition beyond the preceding exact triangle proof.

For any fixed graph $H$ with chromatic number $r\ge 2$, the Erdős-Stone theorem isThe lower bound is the Turan construction: an $(r-1)$-partite graph cannot contain $H$. To describe the upper-bound proof, fix an edge-density excess above $1-1/(r-1)$. Apply a regularity partition with an error parameter much smaller than that excess and a positive density threshold. Delete irregular and low-density pairs; the resulting reduced graph still has density above the Turan threshold, so it contains $K_r$. The corresponding $r$ vertex classes form pairwise regular, positive-density pairs. The embedding argument successively chooses vertices with large neighborhoods in every remaining class; regularity discards only a small exceptional set at each choice. With the parameters sufficiently small and $n$ sufficiently large, this embeds a complete $r$-partite graph with $|V(H)|$ vertices in each part, and therefore a properly colored copy of $H$. This explains why chromatic number, rather than the exact shape of $H$, controls the leading quadratic term.

For example $\chi (C_5)=3$, so forbidding a five-cycle still allows asymptotically $n^2/4$ edges, and exceeding that density by any fixed positive fraction eventually forces a five-cycle. For $K_r$ the exact Turan theorem strengthens the asymptotic statement. For bipartite $H$, the theorem gives only $o(n^2)$, leaving an important finer problem: for example $K_{s,t}$-free graphs have upper bounds of order $n^{2-1/s}$ from counting common neighborhoods. Extremal results consequently range from exact finite bounds to asymptotic density thresholds and stability questions about near-extremal structure.

The Turán graph $T_r(n)$ is the complete $r$-partite graph with part sizes differing by at most one. Turan theorem states that a graph on $n$ vertices containing no $K_r$ has at most $e(T_{r-1}(n))$ edges, with equality precisely for that balanced complete multipartite graph.

Here is a symmetrization proof, including equality. Choose a $K_r$-free graph with the maximum number of edges. Replacing a vertex $u$ by a nonadjacent twin of a nonadjacent vertex $v$ preserves $K_r$-freeness: a clique using the replacement would give the same clique using $v$. Thus nonadjacent vertices must have equal degrees, or cloning the higher-degree vertex increases the edge count. In fact their neighborhoods are identical. Otherwise choose $w$ adjacent to $u$ but not $v$. Cloning $u$ to $v$ preserves the total number of edges but lowers $w$'s degree by one, leaving $v$'s degree unchanged. The still nonadjacent pair $w,v$ now has unequal degrees, allowing an edge-increasing clone and contradicting maximality.

Nonadjacency is consequently an equivalence relation, and the extremal graph is complete multipartite. It has at most $r-1$ parts because choosing one vertex from each part forms a clique. For $n\ge r-1$, using fewer parts cannot be extremal if a part can be split. Finally its number of edges is $\frac{1}{2}(n^2-\sum n_i^2)$, maximized uniquely by balanced sizes: moving a vertex from a part at least two larger than another decreases the sum of squares. This proves the theorem and its equality characterization. The cases with fewer vertices than the forbidden clique are immediate.

The Erdős-Stone theorem says that, for a fixed graph $F$ with chromatic number $q\ge 2$,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$.

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\ge 2$.

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 givesA 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 giveIf $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,\dots ,V_r$ of $G_n$.

The number of possible crossing edges is $\frac{1}{2}(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\to 0$ 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. ThusThis 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.

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,\dots ,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,This proves the minimum degree of an extremal forbidden-subgraph graph. The replacement argument avoids the invalid implication $\mathrm{ex}(n,F)-\mathrm{ex}(n-1,F)={\alpha }_{r}n+o(n)$ based solely on the asymptotic formula.

A colour-critical vertex also bounds the maximum degree. Suppose a vertex $x$ of $H_n$ has $d(x)\ge {\alpha }_{r}n+\epsilon n$ for some fixed $\epsilon >0$. Since the core omits only $o(n)$ vertices and all its classes have size $n/r+o(n)$, $x$ has at least $\epsilon 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:

Symmetrization for an arbitrary real coefficient. Among graphs maximizing $f(G)=e(G)-c{k}_3(G)$, choose one maximizingFor a vertex $x$, put $L(x)=d(x)-ce(G[N(x)])$. This is the contribution of edges and triangles in a graph containing $x$. If $u,v$ are nonadjacent, Zykov symmetrization replacing $u$ by a clone of $v$ changes $f$ by $L(v)-L(u)$; the opposite replacement changes it by $L(u)-L(v)$. Maximality implies $L(u)=L(v)$, so both changes preserve $f$.

Let $S=N(v)\setminus N(u)$ and $T=N(u)\setminus N(v)$. In the first replacement the vertex degrees in $S$ increase by one and those in $T$ decrease by one; in the opposite replacement these changes reverse. The changes to $d(u{)}^2+d(v{)}^2$ cancel when the two replacements are added. Since $(d+1{)}^2+(d-1{)}^2-2d^2=2$,If the two vertex neighbourhoods differ, one replacement increases $Q$, a contradiction. Thus every pair of nonadjacent vertices has the same vertex neighbourhood. Nonadjacency, with equality allowed, is an equivalence relation: if $u$ and $v$ are nonadjacent and $v$ and $w$ are nonadjacent, their identical vertex neighbourhoods forbid $uw$ as well. Its classes are independent sets and every cross-class edge is present. ThereforeThis edge-triangle symmetrization works for either sign of $c$.

The exact supporting line. For $n\ge 3$, writeWe prove the triangle support line between bipartite and tripartite Turan graphs by maximizing $e-c_{\ast }{k}_3$. First $c_{\ast }\ge 2/n$. For $n=3,4,5$, its values are respectively $1,1/2,1/2$. For $n\ge 6$, the exact balancing of the Turán graph gives $e_3\ge n^2/3-1/3$, while $e_2\le n^2/4$ and the arithmetic-geometric mean inequality gives $t_3\le n^3/27$. Hence

By edge-triangle symmetrization a maximizing graph can be taken complete multipartite graph; among such maximizers use one with the fewest nonempty parts. If there are at least four parts, let $a,b$ be the two smallest sizes. Then $a+b\le n/2$. Merging them loses $ab$ edges and $ab(n-a-b)$ triangles in a graph, so the objective changes byThis contradicts the choice of the number of parts. Thus at most three parts remain.

For three part sizes $a\ge b\ge d>0$, the objective isIf $1-c_{\ast }b\le 0$, merging the parts of sizes $a,d$ does not decrease it, again contradicting minimality. If $1-c_{\ast }b>0$ and $a-d\ge 2$, transferring one vertex from the largest to the smallest part raises $ad$ by $a-d-1>0$ and strictly increases the objective. Thus a three-part maximizer has all sizes differing by at most one, and is $T_3(n)$. A maximizer with at most two parts has objective at most $e_2$, since it has no triangles in a graph and the Mantel theorem bounds its edges. Finally,Therefore every graph satisfies $e(G)-c_{\ast }{k}_3(G)\le e_2$. At the prescribed edge count this givesFor $n\le 2$, the conclusion is simply the nonnegative lower bound zero. All rounding in the Turán graphs has been retained.

One edge above the bipartite threshold. Write $n=2m$. We prove the Triangle lower bound one edge above the Mantel threshold by induction on $m\ge 2$, allowing at least $m^2+1$ edges. For $m=2$, five edges on four vertices give two triangles in a graph, and adding edges preserves this bound.

We will also use the following consequence of an inductive bound: on $2a$ vertices, at least $a^2+q$ edges, for an integer $q\ge 1$, force at least $a+q-1$ triangles in a graph. Delete surplus edges first to leave exactly $a^2+q$. Repeatedly delete an edge in a triangle in a graph until $a^2+1$ edges remain. The Mantel theorem guarantees such a triangle in a graph at every step; each deletion destroys at least one distinct triangle in a graph. Apply the inductive bound to the remaining graph.

Now take exactly $m^2+1$ edges. If every edge lies in a triangle in a graph, the edge-triangle incidence bound gives $3k_3(G)\ge m^2+1$. This is at least $3m$ for $m\ge 3$; the base case was handled separately.

Otherwise choose an edge $uv$ in no triangle in a graph. Its endpoints have disjoint vertex neighbourhoods, so $d(u)+d(v)\le 2m$. Deleting $u,v$ removes exactly $d(u)+d(v)-1$ edges and leaves at least $(m-1{)}^2+1$ edges. If $d(u)+d(v)\le 2m-1$, it leaves at least $(m-1{)}^2+2$ edges, and the strengthened inductive bound gives at least $m$ triangles in a graph already.

If $d(u)+d(v)=2m$, induction gives at least $m-1$ triangles in a graph after deletion. There must be an additional triangle in a graph containing $u$ or $v$. Otherwise both $N(u)$ and $N(v)$ are independent sets; since they are disjoint and cover all vertices, $G$ would be bipartite graph, contradicting $e(G)>m^2$ by the Mantel theorem. HenceThe bound is sharp: add one internal edge to one class of the complete bipartite graph $K_{m,m}$. Its triangles in a graph are precisely that edge together with each of the $m$ vertices in the other class.

Turan theorem states that among all $N$-vertex graphs containing no $K_{r+1}$, the maximum number of edges is attained by the Turán graph $T_r(N)$, the complete multipartite graph whose $r$ part sizes differ by at most one.

Here is the Zykov symmetrization proof. Start with an extremal $K_{r+1}$-free graph. If nonadjacent vertices $u,v$ have different neighbourhoods, replace the lower-degree vertex by a clone of the higher-degree one: delete all its incident edges and join it to precisely the neighbours of the other vertex. This does not decrease the number of edges and cannot create a $K_{r+1}$, because a clique using the clone corresponds to one using the original vertex. Repeating the operation, with the standard tie-breaking that merges equal-neighbourhood classes, produces a complete multipartite extremal graph. It has at most $r$ nonempty parts, since choosing one vertex from each part gives a clique.

If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller changes the number of cross-edges byThus an extremal partition has exactly $r$ parts whose sizes differ by at most one. This is $T_r(N)$ and proves the theorem. For $r=2$ it is Mantel theorem: a triangle-free graph on $N$ vertices has at most $\lfloor N^2/4\rfloor$ edges.

The Turán graph $T_r(n)$ is a complete multipartite graph with $r$ independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when $r>n$.^[ref]

In this example, the independent sets are $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$ and $C=\{c_1,c_2\}$. Count the edges between each pair of parts:Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form $K_4$. Conversely, every choice of one vertex from each part is a triangle in a graph, giving $3\cdot 3\cdot 2=18$ triangles in a graph. Clique exclusion here does not mean triangle-free.

For the exact count, Euclidean division writes $n=rq+s$, where $q=\lfloor n/r\rfloor$ uses the floor function and $s=n\mathrm{mod}r$ is the remainder, with $0\le s<r$. There are $s$ parts of size $q+1$ and $r-s$ of size $q$. For any part sizes $a_1,\dots ,a_r$ summing to $n$, count cross edges by expanding the square:ThereforeFor $n=8,r=3$, we have $q=2,s=2$, giving $(64-2\cdot 9-1\cdot 4)/2=21$. The Quadratic Turan edge bound gives $64/3$ instead: the exact correction subtracts $1/3$.

Balancing is an integer optimization with a simple reason. If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares byso it increases the edge count by $a-b-1$. For eight vertices, parts $4,2,2$ give $20$ edges; moving one vertex produces $3,3,2$ and $21$ edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.

How many edges can we retain while excluding a prescribed clique? For integers $r\ge 1$ and $n\ge 0$, every simple graph on $n$ vertices containing no complete subgraph $K_{r+1}$ satisfiesEquality holds exactly for the Turán graph $T_r(n)$, up to graph isomorphism. Thus the extremal number is $\mathrm{ex}(n,K_{r+1})=t_r(n)$.^[ref]

For example, $T_3(8)$ has independent sets of sizes $3,3,2$ and $21$ edges, as counted in Turán graph. It contains triangles in a graph, but no four-vertex clique. Consequently any simple graph on eight vertices with $22$ edges contains $K_4$, while $21$ edges alone do not force one. Excluding larger cliques permits denser graphs; Mantel theorem is precisely the first nontrivial case.

A short proof outline uses Zykov symmetrization. If an extremizer is not a complete multipartite graph, it has vertices $x,y,z$ with $xy,xz$ absent and $yz$ present. If either $y$ or $z$ has larger vertex degree than $x$, clone that vertex in place of $x$. Otherwise replace both $y,z$ by nonadjacent clones of $x$, gaining $2d(x)-d(y)-d(z)+1>0$ edges. Both contradict extremality; balancing the resulting at most $r$ parts gives $T_r(n)$.^[ref]

The vertex cloning in a graph step preserves clique exclusion because any clique using a clone can substitute its original vertex; nonadjacent clones cannot occur together in a clique. At most $r$ parts can be nonempty, since selecting one vertex from each gives a clique. If fewer than $r$ parts are nonempty and one has at least two vertices, splitting it creates more edges, so it cannot be extremal. For $r=1$ the bound is zero. For $r\ge n$, the Turán graph is $K_n$, and the bound is the total $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges.