Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on vertices can be made bipartite by deleting at most edges?
Source: erdosproblems.com/74
An accepted solution exists. The statement is false.
DISPROVED (LEAN), the site's label, crediting a negative answer found by GPT-6 Astra: a divergent edge-deletion budget forces three-colorability. The corpus accepts the claim, a slow edge-deletion budget forces three colors, on formalized evidence: the pinned Lean development was built here and its compared statement audited against the Statement above, so the problem stands solved and disproved. That evidence certifies the disproof and not the three-color strengthening; the site's acceptance, the preliminary expositions, and the scope of the reconstructed proof are distinguished below. Rödl's positive answer for the budgets is a partial claim, nearly bipartite graphs of infinite chromatic number. On 2026-09-05 the site listed the variant as an open subquestion. The site notes that Erdős offered more for a proof than for a counterexample.