Minimum edge-deletion to bipartite: β(G)/h_G(n), the Max-Cut complement, and the Edwards–Erdős bound

Statement

For a graph $G=(V,E)$ let $b(G)$ denote the maximum number of edges in a bipartite subgraph of $G$ (equivalently, $b(G)=\mathrm{MaxCut}(G)$, the largest edge-cut). Define the edge-deletion-to-bipartite parameter (also called the *bipartite edge frustration*, *edge bipartization number*, or the *Max-Cut complement*) $$\beta(G) \;:=\; e(G) - b(G) \;=\; \min\{\,|F| : F\subseteq E(G),\ G-F \text{ is bipartite}\,\}.$$ $\beta(G)=0$ iff $G$ is bipartite; equivalently, $\beta(G)$ is exactly the minimum number of edges one must delete to destroy every odd cycle of $G$ (an "odd-cycle edge-transversal" — not to be confused with the *vertex*-deletion odd-cycle transversal number, a different, generally incomparable, parameter).

The $h_G(n)$ form (Erdős–Hajnal–Szemerédi 1982 [EHS82], Definition 3.1). For a (possibly infinite) graph $G$, define $$h_G(n) \;:=\; \max_{A} \ \beta(A),$$ the maximum taken over all $n$-vertex subgraphs $A$ of $G$ — i.e. the *worst-case* value of $\beta$ over all size-$n$ finite pieces of $G$. This is the quantity used to formalize "how close to bipartite every finite piece of $G$ can be forced to be" as a function of $n$, and is the object at stake in Erdős #74 — almost-bipartite graph of infinite chromatic number and Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$.

Universal bound (folklore, e.g. Erdős 1967 [8 in Sudakov 2007]). Every graph with $e$ edges satisfies $\beta(G)\le e/2$, i.e. $b(G)\ge e/2$. Proof: a uniformly random bipartition $(V_1,V_2)$ puts each edge across the cut with probability $1/2$; linearity of expectation gives $\mathbb E[\text{cut size}]=e/2$, so some bipartition achieves $\ge e/2$. $K_n$ shows the constant $1/2$ is asymptotically tight in general.

Edwards' bound (C. Edwards 1973). $\mathrm{MaxCut}(G) \ge \dfrac{e}{2} + \dfrac{\sqrt{8e+1}-1}{8}$, i.e. $\beta(G) \le \dfrac{e}{2} - \dfrac{\sqrt{8e+1}-1}{8}$; exact for complete graphs, hence best possible whenever $e=\binom n2$. Erdős conjectured this bound; Edwards proved it (originally via a probabilistic/counting refinement of the random-bipartition argument; Crowston–Jones–Mnich later gave an alternative linear-algebra/pseudo-Boolean proof). The connected-graph form, also called the Edwards–Erdős bound: for $G$ connected with $n$ vertices, $m$ edges, $\mathrm{MaxCut}(G)\ge m/2+(n-1)/4$; for $t$ components, $\mathrm{MaxCut}(G)\ge m/2+(n-t)/4$ — tight for complete graphs on an odd number of vertices. Alon (2000s) showed that for infinitely many $m$ the Edwards bound itself can be improved by $\Omega(m^{1/4})$, resolving a further Erdős conjecture. Poljak–Turzik generalized to edge-weighted graphs: $w(G)/2 + w(T_{\min})/4$, where $T_{\min}$ is a minimum-weight spanning forest.

Complexity. Computing $\beta(G)$ (equivalently $\mathrm{MaxCut}(G)$) exactly is NP-hard: Garey, Johnson & Stockmeyer (1976), *Theoretical Computer Science* 1, 237–267, prove Simple Max-Cut (unweighted Max-Cut) is NP-complete. The Goemans–Williamson SDP-rounding algorithm gives a $\approx 0.878$-approximation to $\mathrm{MaxCut}(G)$; under the Unique Games Conjecture (Khot–Kindler–Mossel–O'Donnell) this ratio is optimal; unconditionally, Håstad's hardness result rules out approximation ratios above $16/17\approx 0.941$. Exactly computable in polynomial time on planar graphs (via $T$-join/matching methods).

Erdős's $H$-free extremal conjectures. Erdős first raised the extremal Max-Cut question ("On even subgraphs of graphs," *Mat. Lapok* 18 (1967), 283–288) and later conjectured (*Proc. 5th British Combin. Conf.*, Congressus Numerantium XV (1976), 169–192) that every triangle-free graph on $n$ vertices satisfies $\beta(G)\le n^2/25$, with equality approached by a balanced blow-up of the $5$-cycle $C_5$ (each vertex $\to$ independent set of size $n/5$, each edge $\to$ complete bipartite graph). Progress: Erdős–Faudree–Pach–Spencer (1988), *J. Combin. Theory Ser. B* 45, 86–98, proved $\beta(G)\le(1/18-\epsilon)n^2$ for triangle-free $G$ and verified the full conjecture whenever $e(G)\ge n^2/5$; Erdős–Győri–Simonovits (1992) and Shearer (1992) improved further; Bondy–Locke (1986) settled the maximum-degree-$3$ case exactly; Balogh, Clemen & Lidický (2021, arXiv:[2103.14179](https://arxiv.org/abs/2103.14179)) proved the general bound $\beta(G)\le n^2/23.5$ and settled the conjecture in the low- and high-density tails ($e/n^2\le 0.2486$ or $\ge 0.3197$); a 2026 computer-assisted paper (arXiv:[2606.28041](https://arxiv.org/abs/2606.28041)) settles small multiples-of-five cases $n\in\{5,10,\dots,200\}$. The general triangle-free $n^2/25$ conjecture remains open as of 2026-07.

$K_4$-free case (proved). Erdős separately conjectured $\beta(G)\le(1+o(1))n^2/9$ for $K_4$-free $G$; Sudakov (2007), *Combinatorica* 27, 509–518 (arXiv:[0706.4101](https://arxiv.org/abs/0706.4101)), proves this exactly: $\beta(G)\le n^2/9$ for every $K_4$-free $n$-vertex $G$, with the unique extremal graph the complete tripartite $K_{n/3,n/3,n/3}$; via Szemerédi's Regularity Lemma this extends asymptotically to every fixed forbidden subgraph $H$ with $\chi(H)=4$. Sudakov further conjectures, for general $K_r$-free graphs, $\beta(G)\le\frac{(r-2)^2}{4(r-1)^2}n^2$ (even $r\ge5$) / $\beta(G)\le\frac{r-3}{4(r-1)}n^2$ (odd $r\ge5$) — open for $r\ge5$.

Sparse / random-graph regime. For sparse graphs with no short cycles, Alon–Bollobás–Krivelevich–Sudakov ("Maximum cuts and judicious partitions in graphs without short cycles," *J. Combin. Theory Ser. B* 88 (2003), 329–346) sharpen the $e/2$ bound by an additive term depending on girth. For sparse Erdős–Rényi random graphs $G(n,c/n)$ (average degree $\gamma$) and random $\gamma$-regular graphs, Dembo, Montanari & Sen ("Extremal Cuts of Sparse Random Graphs," *Ann. Probab.* 45 (2017), arXiv:[1503.03923](https://arxiv.org/abs/1503.03923)) prove $\mathrm{MaxCut}(G) = n\big(\gamma/4 + P^\star\sqrt{\gamma/4} + o(\sqrt\gamma)\big)+o(n)$, where $P^\star\approx0.7632$ is the Sherrington–Kirkpatrick spin-glass ground-state constant given by the Parisi formula — obtained via a spin-glass interpolation technique, not a combinatorial argument.

Facts

- $\beta(G)=e(G)-\mathrm{MaxCut}(G)$; the two quantities are exact complements of each other relative to $e(G)$, so every Max-Cut bound is immediately a $\beta$-bound and vice versa. - Terminology varies across sub-literatures: "bipartite edge frustration" / "edge bipartization number" (algorithmic-complexity literature), "line index of balance" (signed-graph balance theory, generalizing Harary's 1953 frustration index — the all-edges-negative special case of signed-graph frustration is exactly $\beta(G)$), or simply "(complement of) Max-Cut" (extremal graph theory). - $\beta$ is additive over disjoint unions ($\beta(G_1\sqcup G_2)=\beta(G_1)+\beta(G_2)$) but is not monotone under taking subgraphs or induced subgraphs in general (removing vertices/edges changes both $e(G)$ and the achievable cut, with no fixed direction) — this non-monotonicity is exactly why $h_G(n):=\max_{|A|=n}\beta(A)$, a *worst-case-over-subgraphs* quantity, is the meaningful object to track for infinite $G$, rather than $\beta$ of the whole (possibly infinite) graph. - NP-hardness is a genuine obstruction to exact computation, but does not obstruct the extremal-combinatorics program above, which bounds $\beta(G)$ as a function of $n$ (and forbidden substructure) uniformly over *all* graphs in a class, sidestepping per-instance computation entirely. - The odd-cycle-disjointness lower bound: if $G$ contains $k$ pairwise vertex-disjoint odd cycles, then $\beta(G)\ge k$, since each odd cycle needs at least one deleted edge to become bipartite and vertex-disjoint cycles cannot share a deleted edge. This is the mechanism erdosproblems.com/111 uses to show $\chi(G)=\aleph_1 \Rightarrow h_G(n)\gg n$ (any $\aleph_1$-chromatic graph contains $\aleph_1$-many vertex-disjoint odd cycles of some fixed length, per Erdős #74 — almost-bipartite graph of infinite chromatic number's Facts section) — i.e. the *only* general-purpose combinatorial lower-bound tool for this parameter found in this literature trail is this disjoint-odd-cycle-packing argument. - Rödl (1982), *Combinatorica* 2, 377–383, builds — for every fixed $\epsilon>0$ — a graph of chromatic number $\aleph_0$ with $h_G(n)\le \epsilon n$ for all $n$ (settling the *linear* regime of Erdős #74 — almost-bipartite graph of infinite chromatic number affirmatively), and separately proves the full hypergraph analogue of the EHS82 conjecture; the sub-linear regime ($f(n)=o(n)$, all the way down to arbitrarily slow $f(n)\to\infty$) remains open, per Erdős #74 — almost-bipartite graph of infinite chromatic number.

Technique

When it applies. Whenever a proof needs to certify, either (a) that a graph (or every graph in some family) is *close* to bipartite — i.e. an upper bound on $\beta(G)$/lower bound on $\mathrm{MaxCut}(G)$ — or (b) that a graph is *far* from bipartite — a lower bound on $\beta(G)$, typically to obstruct a hoped-for sub-linear or sub-quadratic construction.

Why it works — the upper-bound toolkit

1. Random/greedy bipartition (the base case). A uniformly random 2-coloring achieves expected cut $e/2$ (linearity of expectation over independent edge-crossing events); a deterministic *local-search* variant (repeatedly move any vertex to the side maximizing its own cut-degree; each move strictly increases the cut, so the process terminates at a local optimum) gives the same $e/2$ guarantee constructively, and is the base lemma every refinement below builds on (e.g. Sudakov's Lemma 2.1: an analogous random-partition argument on a *4-partite* graph, exploiting the extra structure, already buys $2e/3$ instead of $e/2$). 2. Edwards-type sharpening. Track a finer statistic than plain expectation (e.g. Edwards' original counting/probabilistic refinement, or the modern local-max-cut observation that at a local optimum no single-vertex flip improves the cut, which forces each vertex to have at least half its neighbors on the opposite side, mechanically producing the $+\Theta(\sqrt e)$ correction term) to push the $e/2$ bound up by a lower-order but non-vanishing additive term; tight exactly for complete graphs, where every vertex's neighborhood is "maximally symmetric." 3. Forbidden-subgraph (Turán-type) sharpening. When $G$ is $H$-free for some fixed dense $H$ (e.g. $K_3$- or $K_4$-free), forbidding $H$ caps the *local* edge-density around any vertex or triangle, which can be fed through a neighborhood-density + Cauchy–Schwarz argument (Sudakov's Lemma 2.2–2.4: bound the sum of common-neighborhood sizes across a triangle by an averaging/Cauchy–Schwarz argument, then apply the base random-bipartition lemma *recursively* inside each triangle-free neighborhood) to buy a bound with a strictly smaller leading constant than $1/2$; combining two such lemmas via a convex combination weighted to optimize the worst case (Sudakov's $3/7,4/7$ combination of inequalities (1) and (2), later refined to $a=1.38$) is the specific mechanical trick that turns two incomparable partial bounds into one that is tight on the actual extremal example. 4. Regularity-lemma bootstrap. Once a bound is proved exactly for $K_r$-free graphs, Szemerédi's Regularity Lemma transfers it *asymptotically* to graphs forbidding any fixed subgraph $H$ with $\chi(H)=r$: build an auxiliary "reduced graph" on the regularity clusters, apply the $K_r$-free bound there (a $K_r$ in the reduced graph, by the regularity/embedding lemma, would force an actual copy of $H$ in $G$), and translate the resulting few "bad" edge-deletions in the reduced graph back into $O(\epsilon n^2)$-many actual deletions in $G$ (Sudakov's Corollary 1.2 proof, the standard Komlós–Simonovits regularity-method template). 5. Spin-glass interpolation (random-graph regime). For $G(n,p)$/random regular graphs, rather than a combinatorial construction, an analytic interpolation between the graph's cut-optimization problem and the Sherrington–Kirkpatrick mean-field spin-glass model pins the exact leading-order Max-Cut constant to the (numerically known, Parisi-formula-computed) SK ground-state energy — a fundamentally different (statistical-physics) proof technique from 1–4 above, used specifically because combinatorial extremal methods do not resolve the *exact constant* (only bounds) in the random setting.

Why it works — the lower-bound toolkit

6. Disjoint odd-cycle packing. To show $\beta(G)$ (or $h_G(n)$) must be large, exhibit many pairwise vertex-disjoint odd cycles inside $G$ (or inside some $n$-vertex subgraph): each contributes an unavoidable, non-shareable deletion. This is the *only* lower-bound mechanism identified in this literature trail, and it is what rules out sub-linear $h_G(n)$ once chromatic number is pushed to $\aleph_1$ (via the fact that sufficiently-high uncountable chromatic number forces uncountably many disjoint odd cycles of one fixed length) — see Erdős #74 — almost-bipartite graph of infinite chromatic number, Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$. Whether an analogous (necessarily different, since it must fail) obstruction rules out sub-linear $h_G(n)$ for merely $\aleph_0$-chromatic $G$ is exactly the open content of Erdős #74 — almost-bipartite graph of infinite chromatic number.

What it does NOT give. Exact values (NP-hard in general; open even asymptotically for the flagship triangle-free $n^2/25$ conjecture after 45+ years); no known combinatorial technique currently closes the gap between Rödl's linear $h_G(n)\le\epsilon n$ upper-bound construction and the open sub-linear regime of Erdős #74 — almost-bipartite graph of infinite chromatic number — the disjoint-odd-cycle lower bound is provably insufficient there, since it is exactly what *fails* to apply once chromatic number is restricted to countable $\aleph_0$ (unlike $\aleph_1$).

Related

- Erdős #74 — almost-bipartite graph of infinite chromatic number — the open Erdős–Hajnal–Szemerédi problem asking whether $\chi(G)=\aleph_0$ is compatible with $h_G(n)=o(g(n))$ for every unbounded $g$; this concept page is the general theory ($\beta(G)$/Max-Cut, upper- and lower-bound toolkits) underlying that problem's central object, reusing its already-vetted EHS82/Rödl/erdosproblems.com sourcing. - Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$ (not yet a page in this wiki; forward reference) — the quantitative $\aleph_1$-chromatic dual, where the disjoint-odd-cycle lower bound (Facts, above) forces $h_G(n)\gg n$; EHS82 built $h_G(n)\ll n^{3/2}$ there, Erdős conjectured $\ll n^{1+\epsilon}$. - Liu–Montgomery (2020/2023) — Erdős–Hajnal odd-cycle reciprocal-sum problem — a structurally different but thematically sibling "chromatic number forces odd-cycle structure" result (sublinear expanders + adjuster gadgets, not the frustration/Max-Cut machinery of this page). - De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs — candidate tool for transferring an infinite-chromatic-number hypothesis into a finite $h_G(n)$ statement, as already used to resolve the sibling problem Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the post-1985 semi-random sparsification method that is the natural modern candidate for pushing Rödl's 1982 linear $h_G(n)\le\epsilon n$ bound below linear, since Rödl's original 1982 construction predates the nibble method. - The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs — the 1959 probabilistic-deletion technique whose "delete an edge from each bad short cycle, union-bound survival of the target invariant" shape is the closest known template for constructing a graph with small $h_G(n)$ while preserving large chromatic number.