Skip to content

Erdős Problem #127

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

A bipartite subgraph of an undirected graph consists of edges crossing some two-colour partition of its vertices. Its maximum possible number of edges is the graph's maximum cut. For each number \(m\) of edges, consider the minimum of the maximum-cut size over all graphs with exactly \(m\) edges, allowing arbitrarily many vertices.

Edwards proved that every such graph contains a bipartite subgraph with at least

\[ \frac m2+\frac{\sqrt{8m+1}-1}{8} \]

edges. Erdős #127 asks whether for infinitely many \(m\) there is an unbounded improvement beyond this expression, uniformly over all graphs with that edge count. The excess \(f(m)\) must be guaranteed for every graph of that edge count, not merely witnessed by one convenient graph.

A small example

The triangle \(K_3\) has three edges and maximum cut two. Its Edwards expression equals

\[ \frac32+\frac{\sqrt{25}-1}{8}=2, \]

so the excess is zero. Complete graphs give infinitely many edge counts where Edwards's lower bound is tight, up to rounding. This does not preclude a different infinite sequence of edge counts on which the excess grows.

For an arbitrary graph \(G\), choosing a uniformly random vertex bipartition retains each edge with probability one half. This proves the elementary bound \(\mathrm{MaxCut}(G)\ge m/2\), but not Edwards's square-root correction.

What is known

PROVED. Noga Alon, Bipartite subgraphs, Combinatorica 16 (1996), 301–311, establishes the required unbounded excess. The original Princeton author publication record states that there exists an absolute constant \(c>0\) such that, for every sufficiently large integer \(t\), every graph with exactly \(2t^2\) edges contains a bipartite subgraph with at least

\[ t^2+\frac t2+c\sqrt t \]

edges. Edwards's bound at \(m=2t^2\) is strictly below \(t^2+t/2\). Hence the excess is at least \(c\sqrt t\), which tends to infinity. This is an exact source-level deduction of the required subsequence.

Alon also establishes an \(O(m^{1/4})\) general upper order for the excess, and his paper gives sharp-order bounds for maximum cuts in triangle-free graphs. These related results do not determine the best leading constant in the arbitrary-graph excess.

GCL's current state

The pinned and maintained Erdős #127 classify it PROVED. The original authenticated issue is #1396. The 1996 publisher record and precise \(2t^2\) edge-count theorem were inspected. Its full extremal-graph proof has not been independently reconstructed, and no completed formal statement from an unadmitted upstream branch is promoted to GCL certification.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded proof-replay task is to substitute \(m=2t^2\) into Edwards's expression and prove

\[ \frac{\sqrt{16t^2+1}-1}{8}<\frac t2 \]

for every positive integer \(t\). Consequently, importing Alon's theorem gives \(f(2t^2)\ge c\sqrt t\) without any false inference from other edge counts. Independently enumerate graphs on at most five vertices to compute exact maximum cuts and compare with Edwards's bound. Acceptance: all graphs at a fixed \(m\) contribute to the minimum, and the triangle gives equality; stop at these semantic checks.

Sources and claim boundaries

No new maximum-cut inequality, independent full proof verification or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1396 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction