Skip to content

Erdős Problem #718

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

Erdős, Hajnal and Mader asked whether there exists one absolute constant C such that EVERY finite graph on n vertices with at least \(Cr^2n\) edges contains a subdivision of \(K_r\). The maintained source says PROVED independently by Komlós–Szemerédi and Bollobás–Thomason (1996). 'Subdivision' means internally vertex-disjoint replacement paths, not merely a graph minor with connected branch sets.

A small example

For r=4,n=4, a \(K_4\) subdivision requires the complete \(K_4\) itself, with six edges. \(K_4\) has six edges and contains the required subdivision; \(K_4\) minus one edge has five edges and cannot contain a K4 subdivision on only four vertices. This finite threshold check is unrelated to the unknown optimal absolute C for arbitrary r,n.

What is known

Mader's older bound required roughly \(2^{\binom{r}{2}}n\) edges, exponentially worse than quadratic in r. Komlós–Szemerédi [KoSz96] and Bollobás–Thomason [BoTh96] independently established the \(Cr^2n\) sufficient condition. Dirac had earlier shown 2n−2 edges suffice for a K4 subdivision and conjectured a bound for K5. The exact constants, strict-versus-nonstrict conditions and small-n vacuity require original paper inspection; the catalogue abstracts are not new GCL proofs.

GCL's current state

The authenticated original source return remains in its original BOUNDED_TASK_DESIGNED state. This is an editorially reviewed explanatory article in protected EC-BULK-005-R7, subject to that PR's protected merge. Original research theorem proofs and any external formalizations are attributed to their authors, not newly GCL-certified. The historical source and proof-review limitations recorded in the return remain applicable.

What remains

ERDOS-718-TOPOLOGICAL-MINOR-SOURCE. Source-lock one 1996 theorem and its absolute C with graph simplicity and edge threshold, verify an exact n=4,r=4 fixture, and distinguish topological subgraph from general minor. Acceptance is a theorem-proof interface, no new bound.

Sources and claim boundaries

Maintained source #718 · GCL issue report. Full original mathematical arguments not independently replayed; no independent theorem proof certification.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1989 — 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