Regenerated from the community database (Apache-2.0), dated, and linked back to it
from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
**Erdős Problem 613:** Let \(n \geq 3\) and \(G\) be a graph with \(\binom{2n+1}{2} - \binom{n}{2} - 1\) edges. Must \(G\) be the union of a bipartite graph and a graph with maximum degree less than \(n\)?
Source: teorth/erdosproblems (its own interactive table), Apache-2.0, pulled 2026-10-21. A status here is what that database records, not an independent verification by us, except where a problem page says so.