GPT 6 Astra Ultra attempt on Math-5765
mathematicsErdős problemscontributionManuscript
Contents
Erdős Problem #608: a rational-parameter counterexample for $C_5$ edges
Exact construction and edge counts, 24 September 2026.Statement and source
Must every graph with $n$ vertices and more than $n^2/4$ edges have at least $2n^2/9$ edges lying in a $5$-cycle? No. We use a rational choice of parameters in the Füredi--Maleki construction recorded as Construction 2 by Grzesik--Hu--Volec. This avoids rounding issues and supplies an explicit $168$-vertex counterexample. It is a reconstruction, not a new extremal result.The graph
For a positive integer $t$, take four disjoint vertex sets with sizes \[|A|=4t,\quad |B|=7t,\quad |C|=7t,\quad |D|=10t. \] Put in every edge between $A,B$, every edge between $B,C$, every edge between $C,D$, and every edge within $D$. There are no other edges. Thus $n=28t$ and \[ e(G)=28t^2+49t^2+70t^2+\binom{10t}{2} =197t^2-5t. \] Since $n^2/4=196t^2$, the edge hypothesis holds whenever $t\geq6$.Exactly which edges lie in a pentagon
Removing the edges internal to $D$ leaves a bipartite graph, with parts $A\cup C$ and $B\cup D$. Consequently every odd cycle must use an internal $D$ edge. No $5$-cycle contains a vertex of $A$. Otherwise choose an internal $D$ edge on that cycle and remove it. The remaining four-edge path joins two vertices of $D$ and passes through a vertex of $A$. But the distance between $A$ and $D$ in the graph is three: every such route must pass through $B$ and $C$. A path from $D$ through $A$ back to $D$ therefore has at least six edges, a contradiction. In particular none of the $28t^2$ edges between $A$ and $B$ lies in a $C_5$.Every other edge does lie in a $C_5$. For an edge $bc$ with $b\in B,c\in C$, choose $c'\in C\setminus\{c\}$ and distinct $d,d'\in D$; then \[b,c,d,d',c',b \] is a pentagon. For a prescribed edge $cd$ between $C,D$, the same pattern works after choosing $b,c',d'$ distinct as indicated. Finally every internal $D$ edge lies in a pentagon entirely within the clique $D$, since $|D|\geq5$. All cycles just listed have five distinct vertices. The exact number of edges lying in a pentagon is therefore \[e_{C_5}(G)=49t^2+70t^2+\binom{10t}{2}=169t^2-5t. \] This is strictly smaller than \[\frac29n^2=\frac{1568}{9}t^2, \] because $1568/9-169=47/9>0$.