Skip to content

Erdős Problem #1077

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: disproved (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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

A graph is nearly regular if its vertices have degrees of comparable size. More precisely, a graph with positive minimum degree \(\delta\) and maximum degree \(\Delta\) is \(D\)‑balanced when \(\Delta\le D\delta\).

Erdős Problem #1077 originally asked whether every graph with at least \(n^{1+\alpha}\) edges contains a large \(D\)‑balanced subgraph with comparably many edges, on more than \(n^{1-\alpha}\) vertices.

The difficulty is that the literal statement is not quite the best mathematical formulation. The maintained catalogue discusses a mismatch in the exponent and quantifiers. The correct general scale of the largest guaranteed nearly regular subgraph is proportional to \(n^\alpha\), not \(n^{1-\alpha}\).

A small example

A complete bipartite graph \(K_{a,b}\) connects every vertex on one side to every vertex on the other. Set

\[ a=\lceil2n^\alpha\rceil,\qquad b=n-a, \qquad0<\alpha<\frac12. \]

For sufficiently large \(n\), its \(ab\) edges exceed \(n^{1+\alpha}\). We can prove that every \(D\)‑balanced subgraph \(H\) with an edge, not just a complete bipartite subgraph, has at most \((D+1)a\) vertices.

Suppose \(H\) has \(a'\le a\) vertices on the small side and \(b'\) on the large side, with positive minimum degree \(\delta\) and maximum degree \(\Delta\le D\delta\). Count its edges twice:

\[ b'\delta\le |E(H)|\le a'\Delta\le Da'\delta. \]

It follows that \(b'\le Da'\) and hence

\[ |V(H)|=a'+b'\le(D+1)a=O_D(n^\alpha). \]

An isolated vertex would force \(\delta=0\) and therefore all degrees zero under the \(D\)‑balance definition, contradicting the existence of an edge.

Because \(\alpha<1/2\), this upper bound is smaller than \(n^{1-\alpha}\) for sufficiently large \(n\). This is an elementary, independently checked obstruction to the literal original vertex-count exponent.

What is known

Erdős and Simonovits investigated regularizing dense graphs in 1970. The maintained catalogue marks the original question disproved and explicitly discusses likely transcription or intent issues.

It credits Jiang and Longbrake (2025) with the corrected lower-bound scale: a \(6\)‑balanced subgraph on at least a constant multiple of \(n^\alpha\) vertices, with suitable edge-density control. That general positive theorem is external and has not been independently proved here.

GCL's current state

Authenticated source audit #2348 now includes the full bipartite double-counting proof, correcting an earlier incomplete argument. The frozen Lean transcription labels the literal assertion false but contains an unproved theorem body.

The obstruction above is a bounded rigorous mathematical argument. It is not an independent replay of the sharp Jiang–Longbrake theorem or a claim to settle every possible corrected version.

What remains

Primary-source review must determine what Erdős and Simonovits intended by the parameters \(\varepsilon,\alpha,D\), then verify Jiang and Longbrake's precise quantifiers, construction and \(6\)‑balanced theorem. A corrected mathematical statement should be admitted alongside, not confused with, the disproved original.

Sources and claim boundaries

The manuscript remains an unaccepted draft; only the elementary counterexample argument is independently established here.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2348 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned 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