Erdős Problem #744
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory, chromatic number.
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
Fix chromatic number k≥4. Among n-vertex k-CRITICAL graphs, meaning all proper subgraphs have chromatic number below k, let \(f_k(n)\) be the smallest number of edges whose deletion makes such a graph bipartite. Erdős–Hajnal–Szemerédi conjectured \(f_k(n)\)→∞ as n→∞. This is DISPROVED: Rödl–Tuza showed \(f_k(n)=\binom{k-1}{2}\) for all sufficiently large admissible n (as recorded in the maintained catalogue), a constant depending on k.
A small example
The odd cycle \(C_5\) is 3-critical, and deleting ONE edge makes it a path and hence bipartite, so f_3(5)=1. For \(K_4\), which is 4-critical, deleting two same-part edges leaves \(K_{2,2}\), showing \(f_4(4)\le2\); at least two deletions are needed because a bipartite graph on four vertices has at most four edges versus K4's six. Thus \(f_4(4)=2\), and the asymptotic source value 3 for k=4 applies only for sufficiently LARGE n.
What is known
The maintained #744 credits Rödl–Tuza [RoTu85] with the constant extremal result \(f_k(n)=\binom{k-1}{2}\) for large n. Gallai and Lovász obtained earlier n-dependent upper bounds, superseded on the divergence question. The distinction between k-critical and merely k-chromatic graphs is essential; changing to all k-chromatic graphs changes the minimization and permits irrelevant isolated vertices. Original Rödl–Tuza proof pages are not independently replayed.
GCL's current state
The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.
Critical source-scope distinction: Rödl–Tuza k-critical fixed k sufficiently large n; small n different.
What remains
ERDOS-744-K_CRITICAL_BIPARTITE_DELETION. Verify \(f_4(4)=2\) by graph enumeration and exact bipartite edge maximum, then locate Rödl–Tuza's large-n construction and lower bound with precise admissible n. Avoid applying asymptotic equality at n=4.
Sources and claim boundaries
Maintained Erdős #744; original issue-bound GCL audit. Primary full proof pages not all inspected; no protected publication, real browser mathematics validation or V2 admission.
Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2015 — 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.