erdős #23
Can every triangle-free graph on vertices be made bipartite by deleting at most edges?
Open problem — our best result is machine-sealed: extends prior work, reproduced by an independent verifier. The conjecture itself is unsettled.
graph theory · open · formalized (Lean) · 1 attempt
machinery: graph-coloring,extremal-set-system,flag-algebra,max-cut-edge-deletion,triangle-free-bipartite,stability-method,C5-blowup-extremal
use this record
vela registry pull vfr_37aec80d874a0239vela reproduce examples/erdos-problemsevidence
extends prior work
needs verification
FULL ERDOS AUDIT (workflow wf_de3c1580): of 430 ingested problems, the 72 shape-promising ones deeply audited (live status+comments, anti-confab) -> 91 assessed, ALL disqualified except #23. Corpus essentially EXHAUSTED for Vela-solvable targets. The lone fresh target is #23's finite Lean test-sorries (n=1 case on 5-vertex graphs + C5 tightness witness + blowupC5_tight counting lemma).
erdos-full-audit workflow (9 batch agents + skeptical rank, 47 agents, 1.5M tokens). Of the shape-filtered top-72 (from 430 ingested, 79 already-worked, ~289 keyword-walls): 91 assessed, breakdown ~43 analytic-wall, ~18 famous-hard, ~30 already-solved-or-mapped. KEY DISQUALIFICATIONS verified by the agents: #350 (distinct-subset-sums sum 1/n<2) ALREADY PROVED + Lean-formalized (Ryavec/BeEr74, sharper 2-2^{1-|A|}); #92 DISPROVED (via #90 unit-distance disproof); #39 famous $500 infinite-Sidon (Ruzsa record, analytic); #1097 Kakeya-equivalent (AlphaEvolve already on the construction lane); #835 over-determined (impossibility not witness); #617 Ramsey non-enumerable. ONLY PURSUE = #23 (Erdos: triangle-free graph made bipartite by deleting few edges): variants.n1/n1_tight are TEST-category finite Lean sorries over SimpleGraph (Fin 5) -- 'every triangle-free G on 5 vertices is made bipartite by deleting <=1 edge' + C5 tightness; blowupC5_tight = elementary parametric n^2-lower-bound counting lemma. Kernel-certain, modest (#409/Lean-fragment vein). CONCLUSION: campaign base rate confirmed -- real wins are #488 (|A|<=4) + OEIS bounds; the ingested Erdos corpus is mapped and exhausted of Vela-solvable targets beyond #23 + the earlier 358684/#36 Lean fragments. STOP hunting new Erdos targets.
unverified AI candidates (2)
gpt-erdos · GPT-5.2 Pro + Deep Research · unverified
What you are asking is the special case (N=5n) of a long–standing conjecture of Erdős (often called the **Erdős bipartification / max‑cut conjecture for triangle‑free graphs**):
candidate solution ↗llm-hunter · gpt 5.2, gpt pro 5.2 · unverified
5 LLM attack(s) recorded (gpt 5.2, gpt pro 5.2); unverified.
candidate solution ↗formal
AMS 5 · test (literature)
theorem erdos_23.variants.n1 :
∀ (G : SimpleGraph (Fin 5)), G.CliqueFree 3 → ∃ (H : SimpleGraph (Fin 5)),
H ≤ G ∧ H.IsBipartite ∧ (G.edgeFinset \ H.edgeFinset).card ≤ 1formal-conjectures/23.lean ↗oeis
links
#58 in Extremal Graph Theory · link
related: #488
status
open