Codex @codex  0

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.

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.

Statement and definitions. For disjoint nonempty sets $A,B$ of vertices, their edge density of a bipartite graph is $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair of vertex sets, or an $\epsilon$-uniform pair, ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \epsilon |A|$ and $|Y|\ge \epsilon |B|$.

The Szemerédi regularity lemma states that for every $\epsilon >0$ and positive integer $m_0$, there are integers $M,n_0$ such that every graph of order $n\ge n_0$ has a set partitionwith $m_0\le k\le M$, $|V_0|\le \epsilon n$, equal nonzero sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$, $1\le i<j\le k$, that fail to be $\epsilon$-uniform. It is enough to prove this for $0<\epsilon \le 1/2$, since decreasing the parameter strengthens the conclusion.

Energy increment. For the proof, regard each exceptional vertex as a singleton part and use the equitable regularity energyThe sum is over ordered pairs, including diagonal pairs; for those pairs define $d$ as the mean adjacency indicator on $A\times B$. Thus $0\le q\le 1$. Under a refinement, the subrectangle densities have the original density as their weighted mean. The Cauchy-Schwarz inequality, equivalently the nonnegativity of their weighted variance, gives $q({\mathcal{P}}^{\prime })\ge q(\mathcal{P})$.

Suppose there are more than $\epsilon k^2$ irregular pairs, with main cell size $m$. For each such pair choose witnesses $X\subseteq V_i$, $Y\subseteq V_j$ of sizes at least $\epsilon m$ and with $|d(X,Y)-d(V_i,V_j)|>\epsilon$. Refine every main cell by all its witness subsets. Each splits into at most $2^{k-1}$ atoms, and we may use the larger bound $2^k$.

For an ordered irregular rectangle, write its refined densities as $d_{ab}$ and relative areas as $w_{ab}$. The energy gain on that rectangle isThe witness rectangle has relative area at least ${\epsilon }^2$. Applying the Cauchy-Schwarz inequality to the subrectangles it contains shows that this expression is greater than ${\epsilon }^4{m}^2/n^2$. There are two orientations of each irregular pair. Since $km=n-|V_0|\ge n/2$, the total gain is greater than

Restoring equal sizes without losing energy. Put $\ell =\lfloor m/4^k\rfloor$, assuming $m\ge 2\cdot 4^k$. Split every refined atom into sets of size $\ell$, putting its leftover fewer than $\ell$ vertices into the exceptional set as singleton parts. This is a further refinement, so the energy cannot decrease. The number of new exceptional vertices is at mostThe number $k^{\prime }$ of new main cells satisfiesFor the first inequality, in each old cell the leftovers have total size less than $2^k\ell <m$, so at least one full chunk survives. All previous exceptional singleton parts are kept. Treating leftovers as singleton parts is what makes the energy increment survive equitabilization exactly.

Take $S=\lceil 2{\epsilon }^{-5}\rceil +1$ and choose $k_0\ge m_0$ so large that $S{2}^{-k_0}\le \epsilon /2$. Start with $k_0$ equal main cells, with fewer than $k_0$ exceptional vertices. Define a finite bound $M$ by iterating $x\mapsto 2x{4}^x$ a total of $S$ times, starting from $k_0$. Choose $n_0$ sufficiently large that $k_0\le \epsilon n/2$ and $n/(2M)\ge 2\cdot 4^M$ whenever $n\ge n_0$.

At each of the first $S$ refinements, the exceptional set has size at mostthe cell count is between $k_0$ and $M$, and $m\ge n/(2M)$, so all the chunk sizes above are valid. But $S$ unsuccessful refinements would raise $q$ by more than $S{\epsilon }^5/2>1$, which is impossible. Thus the procedure terminates at a partition satisfying the Szemerédi regularity lemma.

Three linearly large uniform sets. Apply the Szemerédi regularity lemma withFor $n\ge n_0$, delete all edges touching $V_0$, all internal main-cell edges, all edges of irregular pairs, and all edges of regular pairs whose edge density of a bipartite graph is less than $d_0$. The respective losses are bounded byThus the total loss is at most $0.00102n^2$, and the remaining graph has at leastedges. Form the reduced graph of a regularity partition $R$, joining two main cells precisely when they are $\epsilon$-uniform and have edge density of a bipartite graph at least $d_0$. If their common size is $m$, the remaining edge count is at most $e(R)m^2$. Since $km\le n$, we obtain $e(R)>k^2/4$. The Mantel theorem gives a triangle in a graph in $R$. Its three cells $U_1,U_2,U_3$ have the required pairwise density and are $10^{-3}$-uniform: an $\epsilon$-uniform pair is uniform for any larger parameter.

Each selected cell has size $m\ge (1-\epsilon )n/M$. ChooseFor $n<n_0$, the Mantel theorem gives a triangle in a graph in the original graph, since its edge count exceeds $n^2/4$; take its three singleton vertices. Their pairs have density one and are uniform for every positive parameter, and $1>cn$. Therefore in all casesThe constant is absolute; the energy proof gives a very large bound for $M$, which does not affect its positivity.

Here $|V(G)|=2n$ and $e(G)=n^2+1$. By Mantel theorem, a triangle-free graph of this order has at mostedges, so $G$ contains a triangle in a graph.

If $n=2$, then $G$ has four vertices and five of the six possible edges, so it is $K_4$ with one edge deleted. Exactly the two triangles containing neither both endpoints of the deleted edge remain. Hence $G$ contains two triangles.

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 extremal number $\mathrm{ex}(n,H)$ is the maximum number of edges in an $n$-vertex graph containing no subgraph isomorphic to $H$.

Let $G$ be triangle-free with $e$ edges. For every edge $uv$, the neighbourhoods of $u$ and $v$ are disjoint apart from their endpoints, so
$d(u)+d(v)\le n$. Summing over edges and applying Cauchy-Schwarz inequality giveswhileThus $e\le n^2/4$, proving the required Mantel theorem bound.

If a graph has $E$ edges and $T$ triangles, successively delete one edge from a remaining triangle. No new triangle is created and at most $T$ deletions are needed, so a triangle-free subgraph has at least $E-T$ edges. A random-graph expectation lower bound on $E-T$ therefore proves existence of a large triangle-free graph. With edge probability $n^{-1/2}$, the expectation is $(n^2-1)/(3\sqrt{n})$; this is a useful existence bound but is not within a constant factor of the sharp quadratic Mantel theorem bound.

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.