Erdős Problem #59

Erdős Problem #59: the matching construction for $C_6$

Reconstruction with explicit external inputs, 23 September 2026.

1) Statement

Must the number of labelled $G$-free graphs on $n$ vertices be at most $2^{(1+o(1))\operatorname{ex}(n,G)}$? The answer is negative already for $G=C_6$.

2) Cited inputs and construction

We use the following bounds, as stated in Morris--Saxton, Theorem 2.2: eventually $\operatorname{ex}(n,C_6)<0.6272n^{4/3}$; for infinitely many $m$, some triangle-free, $C_6$-free $H$ has $m$ vertices and $e(H)>0.5338m^{4/3}$. These extremal inputs are not reproved here.

Following their matching construction, replace each vertex by three labelled vertices and each edge independently by any matching between the corresponding triples. There are \[ \sum_{j=0}^3\binom3j^2j!=1+9+18+6=34 \] choices per edge. Distinct choices give distinct labelled graphs.

A lifted six-cycle would project to a cyclically non-backtracking closed walk of length six: immediate reversal would require two matching edges at one lifted vertex. If this projected walk repeats a vertex, its shortest repeated-vertex cyclic segment is a cycle of length at most three. Lengths one and two are excluded by simplicity and non-backtracking, and length three by triangle-freeness. Otherwise the projection is a six-cycle. Both possibilities contradict the choice of $H$.

For $n=3m$, the construction therefore yields $34^{e(H)}$ admissible graphs. Since \[ \frac{0.5338\log_2 34}{0.6272\,3^{4/3}}>1.0001, \] their number exceeds $2^{1.0001\operatorname{ex}(n,C_6)}$ infinitely often, disproving the proposed asymptotic bound.

3) Scope and checks

The argument uses the triangle-free property of the base graph; merely asking the base graph to avoid a six-cycle would not justify the projection step. Labelling is fixed throughout. The finite check enumerates all 34 matchings and all matching lifts of a four-cycle, and checks absence of six-cycles in those lifts. A rational certificate checks the displayed numerical inequality without relying on floating-point rounding.

SOLVED, reconstructing the published counterexample with stated extremal dependencies. This is not a new construction. Neither the general extremal bounds nor any Lean development has been independently verified here.

4) Sources

Problem: https://www.erdosproblems.com/59, checked 23 September 2026. R. Morris and D. Saxton, The number of $C_{2\ell}$-free graphs, https://arxiv.org/html/1309.2927v3, Theorem 2.2 and Proposition 1.4. Their statement includes the triangle-free feature of the Füredi--Naor--Verstraëte construction.

The estimate measures completion using the declared external inputs and is not a correctness probability.

5) COMPLETION ESTIMATE

COMPLETION: 100%