For a finite nonempty family 
of graphs, let 
be the largest number of edges in an 
-vertex graph containing no member of 
as a subgraph. The corrected
Erdős-Simonovits compactness conjecture asserted that, when every member of
contains a cycle, there are a graph 
and a constant 
such that
 |
for all sufficiently large 
. The condition excluding forests avoids elementary counterexamples
to the original formulation (Wigderson n.d.).
An AI-generated proof given by OpenAI (2026) disproved the conjecture even for connected bipartite
graphs. It constructs a finite family 
of connected bipartite graphs, each containing a cycle, such
that
 |
Here 
and 
are big-O notation and
big-Omega notation, respectively. Thus forbidding
the family reduces the extremal number by more than a constant factor compared with
forbidding any individual member.
