Erdős Problem #23
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: falsifiable (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 graph is triangle-free when it contains no three mutually connected vertices. It is bipartite if its vertices can be divided into two classes with no edge inside either class.
Erdős Problem #23 asks whether every triangle-free graph on \(5n\) vertices can be made bipartite by removing at most \(n^2\) edges. The status is FALSIFIABLE: the conjecture remains open, but one explicitly verified finite counterexample would disprove it.
A small example
A cycle on five vertices has no triangle, but it is not bipartite because its cycle length is odd. Removing just one edge leaves a path and makes it bipartite. With \(n=1\) the proposed bound is exactly one edge, and the example attains it.
The balanced blow-up of the pentagon replaces each of its five vertices by an independent set of \(n\) vertices, and joins every pair of vertices in classes corresponding to adjacent positions on the cycle. There are \(5n\) vertices and \(5n^2\) edges. Its maximum cut has \(4n^2\) edges, so precisely \(n^2\) edges must be removed to make it bipartite. The proposed universal bound, if true, would therefore be sharp.
What is known
Balogh, Clemen and Lidický, Max Cuts in Triangle-free Graphs (2021), establish that any triangle-free graph with \(V\) vertices can be made bipartite after removing at most \(V^2/23.5\) edges. With \(V=5n\) this is
That approaches but does not reach the proposed coefficient one. The published methods also establish the target in specific edge-density regimes, without completing the universal conjecture.
GCL's current state
Source audit #1292 compares the original claim and frozen formal statement, including its quantifier over all triangle-free graphs on exactly \(5n\) vertices. It records the elementary pentagon blow-up extremal construction and warns that auxiliary theorem declarations with unfilled proofs do not constitute GCL kernel acceptance.
What remains
Prove the global sharp bound for every triangle-free graph, or exhibit and independently verify a finite graph violating it. The blow-up example demonstrates optimality of the conjectured coefficient, not correctness of the universal claim.
Sources and claim boundaries
- Erdős Problems #23: FALSIFIABLE but not disproved.
- Balogh–Clemen–Lidický (2021), author paper: finite constant improvement, not the open sharp bound.
- GCL source audit #1292: exact sharpness construction, not a universal proof.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1292 — 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.