The Erdős degeneracy conjecture asserted that every fixed bipartite graph
having graph degeneracy at most
satisfies
where
is the largest number of edges in an
-vertex graph
containing no copy of
as a subgraph, and
is big-O notation.
An AI-generated proof given by OpenAI (2026) disproved the conjecture already for . It constructs a fixed connected bipartite graph
with graph degeneracy
at most 2 and constants
such that
for all sufficiently large .
This also disproves the forward implication of the related conjecture that a bipartite
graph
has graph degeneracy at most 2 iff
(Erdős 1981).