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 if and only if 
(Erdős 1981).
