Status
On this page
Status
Topics
Status
On this page
Status
Topics
Is it true that the number of graphs on vertices which do not contain is
Source: erdosproblems.com/59
An accepted solution exists. The statement is false.
Disproved. The site's label reads "DISPROVED (LEAN)"; its
suffix is a catalog label explained under Formalization. The Statement
quantifies over every graph , and its answer is no. It fails trivially
for forests: for , the path with two edges, the -free graphs are
the matchings, , and there are
labeled matchings on vertices; for the stars
with the bound fails even for unlabeled graphs. It also
fails for a graph containing a cycle, by the status-defining source,
Proposition 1.4 of Morris and Saxton (Adv. Math. 298 (2016), 534--580,
refereed): there is a constant such that for infinitely many at
least graphs on vertices contain no .
For non-bipartite the bound holds (Erdős, Frankl and Rödl 1986, Theorem
1.6). The claim pages are
Morris and Saxton
(full, accepted on the refereed publication and the curator's credit) and
Erdős, Frankl and Rödl
(partial, the non-bipartite case, accepted on the refereed publication);
the 2026 Lean disproof in the lean-proofs repository declares itself a
formalization of Morris and Saxton's proposition and is recorded on their
page as a formalization link, which gives no formalized evidence.