Erdős Problem #533
Status Solved · erdosproblems.comLLM status Solved from source status
Erdős problems openaigpt 6 astra ultragpt pro 5.2 100% cataloguedSolvedSolvedStatement
Fix $\delta>0$. The claim is that there exists a constant $c(\delta)>0$ and an integer $n_0(\delta)$ such that for every $n\ge n_0(\delta)$, every simple graph $G=(V,E)$ on $|V|=n$ vertices satisfying \[ K_5\nsubseteq G\quad\text{and}\quad |E|\ge \delta n^2, \] contains a vertex subset $U\subseteq V$ with $|U|\ge c(\delta)n$ such that the induced subgraph $G[U]$ is triangle-free (contains no $K_3$).
Restatement from Math-5718-A2 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 2
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%
gpt pro 5.2 attempt on Math-5718
Let $\delta>0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_5$ and at least $\delta n^2$ edges then $G$ contains a set of $\gg_\delta n$ vertices containing no triangle. A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi, who could prove this is true for $\delta>1/16$, and could further prove it for $\delta>0$ if we replace $K_5$ with $K_4$. They further observed that it fails for $\delta =1/4$ if we replace $K_5$ with $K_7$: by a construction of Erdős and Rogers [ErRo62] (see [620] ) there exists some constant $c>0$ such that, for all large $n$, there is a graph on $n$ vertices which contains no $K_4$ and every set of at least $n^{1-c}$ vertices contains a triangle. If we take two vertex disjoint copies of this graph and add all edges between the two copies then this yields a graph on $2n$ vertices with $\geq n^2$ edges, which contains no $K_7$, yet every set of at least $2n^{1-c}$ vertices contains a triangle. See also [579] and the entry in the graphs problem collection . References [ErRo62] Erdős, P. and Rogers, C. A., The construction of certain graphs . Canadian J. Math. $1962$, 702-707.
FORMAL RESTATEMENT
Fix $\delta>0$. The claim is that there exists a constant $c(\delta)>0$ and an integer $n_0(\delta)$ such that for every $n\ge n_0(\delta)$, every simple graph $G=(V,E)$ on $|V|=n$ vertices satisfying \[ K_5\nsubseteq G\quad\text{and}\quad |E|\ge \delta n^2, \] contains a vertex subset $U\subseteq V$ with $|U|\ge c(\delta)n$ such that the induced subgraph $G[U]$ is triangle-free (contains no $K_3$).QUICK LITERATURE/CONTEXT CHECK
The problem statement says the claim was proved for $\delta>1/16$ by Erdős--Hajnal--Simonovits--Sós--Szemerédi and that the analogous statement with "no $K_5$" replaced by "no $K_4$" holds for every $\delta>0$. Per the integrity rule I do not use any additional literature.ATTACK PLAN
Proof-track ideas. Use local structure forced by forbidding cliques:- In a $K_4$-free graph, every vertex neighbourhood is triangle-free, giving an immediate linear triangle-free subset.
- In a $K_5$-free graph, every common neighbourhood of an edge is triangle-free (Lemma Lemma (Common neighbourhood of an edge is triangle-free)), so it suffices to find an edge with large codegree. Relating codegrees to global density is the hard part.
WORK
FAST REALITY CHECK (small-$n$ computational sanity).
To sanity-check that large triangle-free subsets can occur at fairly high edge density, I generated examples of dense $K_5$-free graphs by a greedy process: start with the empty graph on $n$ vertices, add edges in random order whenever the added edge does not create a $K_5$. For each such graph I computed the exact size of the largest triangle-free induced subgraph by brute force over all vertex subsets (feasible for $n\le 18$). The table shows sample outcomes for three seeds.| $n$ | seed | edges $m$ | $m/n^2$ | max triangle-free subset | ratio |
| 12 | 0 | 47 | 0.3264 | 7 | 0.583 |
| 12 | 1 | 53 | 0.3681 | 7 | 0.583 |
| 12 | 2 | 50 | 0.3472 | 7 | 0.583 |
| 14 | 0 | 64 | 0.3265 | 7 | 0.500 |
| 14 | 1 | 66 | 0.3367 | 8 | 0.571 |
| 14 | 2 | 63 | 0.3214 | 7 | 0.500 |
| 16 | 0 | 86 | 0.3359 | 8 | 0.500 |
| 16 | 1 | 89 | 0.3477 | 8 | 0.500 |
| 16 | 2 | 79 | 0.3086 | 7 | 0.438 |
| 18 | 0 | 104 | 0.3210 | 9 | 0.500 |
| 18 | 1 | 104 | 0.3210 | 9 | 0.500 |
| 18 | 2 | 105 | 0.3241 | 9 | 0.500 |
VERIFICATION
- Lemma Lemma (Common neighbourhood of an edge is triangle-free): explicitly checked that a triangle inside the common neighbourhood of an edge, together with that edge, forms a $K_5$.
- Lemma lem:533-K4: verified that in a $K_4$-free graph, every neighbourhood is triangle-free.
- Computation: brute force for $n\le 18$ checks all subsets, so the reported "max triangle-free subset sizes" are exact for those sampled graphs (the sampling is not exhaustive over all $K_5$-free graphs).
FINAL
UNRESOLVED(i) Strongest proved partial result. In any $K_5$-free graph, the common neighbourhood of any edge is triangle-free (Lemma Lemma (Common neighbourhood of an edge is triangle-free)), so the problem reduces to finding an edge with linear codegree (Lemma Lemma (Reduction to finding a large codegree)). Also, the $K_4$-free analogue is proved by a simple averaging argument (Lemma lem:533-K4).
(ii) First gap (crisp statement). Show that for every fixed $\delta>0$ there exists $c(\delta)>0$ such that any $n$-vertex $K_5$-free graph with at least $\delta n^2$ edges contains an edge of codegree at least $c(\delta)n$ (or otherwise directly produces a triangle-free induced subgraph on $c(\delta)n$ vertices).
(iii) Top 3 next moves. 1. Prove a dichotomy: either $G$ has an edge with linear codegree, or $G$ has "few" triangles; then show "few triangles" implies a linear-size triangle-free induced subgraph by a covering argument. 2. Use stability around the Turán extremal structure for $K_5$-free graphs (complete $4$-partite graphs) to force two large parts whose union induces a triangle-free subgraph. 3. Computationally: for moderate $n$ (say $n\le 30$), use SAT/ILP to search for dense $K_5$-free graphs that minimize the largest triangle-free induced subgraph; look for extremal patterns.
(iv) Minimal counterexample structure. A minimal counterexample at density $\delta$ would be a dense $K_5$-free graph in which every linear-size vertex subset spans a triangle; equivalently, all induced subgraphs on $\ge c n$ vertices contain $K_3$ while still globally avoiding $K_5$. Such a graph would have no edge of linear codegree (else Lemma Lemma (Common neighbourhood of an edge is triangle-free) gives a large triangle-free set) and would likely have a highly pseudorandom neighbourhood structure constrained by $K_5$-freeness.