GPT 6 Astra Ultra attempt on Math-5718

Erdős problem 533. Does every $K_5$-free graph with at least $\delta N^2$ edges contain a triangle-free vertex set of size at least $c_\delta N$?

Status and external construction. No. Balogh and Lenz first disproved this; the sharp asymptotic construction is due to Liu, Reiher, Sharifzadeh, and Staden. We use their geometric construction theorem as an external input, while checking the numerical normalization, quantifiers, and the contrasting $K_4$ case below. Sources: https://www.erdosproblems.com/533 and https://arxiv.org/abs/2103.10423, version 2, Theorem 1.1, checked 24 September 2026.

Precise input and specialization. Write $\alpha_p(G)$ for the largest size of a vertex set inducing no $K_p$. The cited theorem states that for fixed integers $1\leq\ell<p$ there are graphs with two parts of size $m$ each, with \[ \alpha_p(G)=o(m),\qquad e(G[W]),e(G[Z])=o(m^2),\qquad e_G(W,Z)=(\ell/p-o(1))m^2. \] If $\ell\leq p/2$, these graphs contain no $K_{p+\ell+1}$. We do not reprove the high-dimensional geometric construction.

Take $p=3$ and $\ell=1$. Its clique exclusion is exactly $K_5$; its triangle-free independence number is $o(m)$; and with $N=2m$, \[ e(G)\geq(1/3-o(1))m^2=(1/12-o(1))N^2,\qquad \alpha_3(G)=o(N). \] The factor $1/4$ from changing $m$ to $N$ is necessary. The source's density normalized by $\binom N2$ is $1/6$, whereas the present problem uses $N^2$.

Fix $\delta=1/13$. For every positive candidate $c_\delta$, sufficiently large graphs in this sequence satisfy simultaneously $e(G)\geq\delta N^2$ and $\alpha_3(G)<c_\delta N$. They contradict the proposed conclusion. An infinite sequence of even $N$ suffices to refute a statement asserted for every sufficiently large $N$.

Why the forbidden clique matters: a direct neighbouring result. If the graph is $K_4$-free instead, the assertion has a short proof with $c_\delta=2\delta$. Its average degree is at least $2\delta N$, so some vertex has at least that many neighbours. Its neighbourhood is triangle-free, since a triangle there together with the vertex would form a $K_4$. For a $K_5$-free graph the same argument gives only a $K_4$-free neighbourhood. It supplies no triangle-free neighbourhood, and the geometric construction demonstrates that this loss cannot be repaired merely by positive edge density.

Completion estimate. The counterexample and all quantifiers follow from the explicitly stated geometric theorem; that theorem remains an external proof dependency. COMPLETION: 100%