Erdős Problem #600

Erdős Problem 600 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/600

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/600.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/600.tex.

Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an edge contained in at least $r$ triangles. Let $r\geq 2$. Is it true that\[e(n,r+1)-e(n,r)\to \infty\] as $n\to \infty$? Is it true that\[\frac{e(n,r+1)}{e(n,r)}\to 1\] as $n\to \infty$? Ruzsa and Szemerédi [RuSz78] proved that $e(n,r)=o(n^2)$ for any fixed $r$.

1) FORMAL RESTATEMENT

Fix integers $n\ge 1$ and $r\ge 2$. For a simple undirected graph $H$ on vertex set $[n]:=\{1,2,\dots,n\}$, write $t_H(e)$ for the number of triangles of $H$ containing the edge $e$.

Define $e(n,r)$ as the minimal integer $E$ such that every graph $H$ on $n$ vertices satisfying

1. $|E(H)|\ge E$, and
2. $t_H(e)\ge 1$ for every edge $e\in E(H)$,

must contain an edge $e$ with $t_H(e)\ge r$.

Edge case: if $r>n-2$, then no edge in any $n$-vertex graph can lie in $r$ triangles (since $t_H(e)\le n-2$). In this case the defining implication can only hold vacuously, and the natural minimal choice is $e(n,r)={n\choose 2}+1$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records: for fixed $r$, $e(n,r)=o(n^2)$ (Ruzsa--Szemerédi). I do not use additional external results.

3) ATTACK PLAN

• Proof-track idea: understand extremal graphs with bounded triangle-multiplicity per edge ($t_H(e)\le r-1$) but with every edge in a triangle ($t_H(e)\ge 1$). Compare the maximum edge counts for successive $r$.
• Disproof-track idea: attempt to build (for fixed $r$) very dense graphs where every edge lies in many triangles but still keep the maximum per edge below $r$, and see whether successive maxima differ by $O(1)$.
• Computation track: brute force for small $n$ to see how $e(n,r)$ behaves.

4) WORK

Fast reality check (exact computation for $n\le 7$). I exhaustively searched all graphs on $n\le 7$ vertices. For each $(n,r)$ I computed \[ M(n,r):=\max\{|E(H)|: H \text{ on } n \text{ vertices, } 1\le t_H(e)\le r-1 \text{ for all edges }e\}, \] and then $e(n,r)=M(n,r)+1$. The exact values found are: \[ \begin{array}{c|cccc} n & e(n,2) & e(n,3) & e(n,4) & e(n,5) \\\hline 3 & 4 & 4 & 4 & 4 \\ 4 & 4 & 7 & 7 & 7 \\ 5 & 7 & 9 & 11 & 11 \\ 6 & 7 & 13 & 13 & 16 \\ 7 & 10 & 16 & 17 & 19 \end{array} \] (For example, $e(7,4)=17$ means there exists a 7-vertex graph with 16 edges, every edge in at least one triangle, and no edge in 4 triangles, but any such graph with 17 edges forces an edge in at least 4 triangles.)

Lemma 600.1 (reformulation as a maximum).
Let \[ M(n,r):=\max\{|E(H)|: H \text{ on } n \text{ vertices, } 1\le t_H(e)\le r-1 \text{ for all edges }e\}. \] Then $e(n,r)=M(n,r)+1$.

Proof. By definition, $e(n,r)$ is the smallest $E$ such that every graph $H$ with $|E(H)|\ge E$ and $t_H(e)\ge 1$ for all edges contains some edge with $t_H(e)\ge r$. Equivalently, $E-1$ is the largest number of edges for which there exists a counterexample graph $H$ with

1. $|E(H)|=E-1$,
2. $t_H(e)\ge 1$ for all edges, and
3. $t_H(e)\le r-1$ for all edges.

That largest value is exactly $M(n,r)$. Hence $e(n,r)=M(n,r)+1$. $\square$

Lemma 600.2 (monotonicity).
For all $n\ge 1$ and $r\ge 2$:

1. $e(n,r+1)\ge e(n,r)$ (nondecreasing in $r$);
2. $e(n+1,r)\ge e(n,r)$ (nondecreasing in $n$).

Proof. $1$ If a graph has an edge in at least $r+1$ triangles, then it has an edge in at least $r$ triangles. Thus any edge threshold that forces an edge in $r+1$ triangles also forces an edge in $r$ triangles, so the minimal threshold for $r+1$ cannot be smaller: $e(n,r+1)\ge e(n,r)$.

$2$ Suppose we had $e(n+1,r)<e(n,r)$. Take an $n$-vertex graph $H$ witnessing that $e(n,r)$ is minimal, i.e., with $|E(H)|=e(n,r)-1$, every edge in at least one triangle, and no edge in $r$ triangles. Add one isolated vertex to form a graph $H'$ on $n+1$ vertices. Then $H'$ still has $|E(H')|=e(n,r)-1$ edges, every edge still lies in a triangle (unchanged), and still no edge lies in $r$ triangles. This contradicts the definition of $e(n+1,r)$ if $e(n+1,r)\le e(n,r)-1$. Hence $e(n+1,r)\ge e(n,r)$. $\square$

Lemma 600.3 (vacuous range $r>n-2$).
If $r>n-2$ then $e(n,r)={n\choose 2}+1$.

Proof. In any graph on $n$ vertices, every edge $e$ can be extended to a triangle by choosing a third vertex, giving at most $n-2$ possibilities. Hence $t_H(e)\le n-2$ always. If $r>n-2$ then the conclusion "there exists an edge contained in at least $r$ triangles" is impossible for every graph $H$. Therefore the defining implication can only hold when the antecedent is false, i.e., when $|E(H)|\ge e(n,r)$ is impossible. The smallest integer larger than the maximum possible number of edges ${n\choose 2}$ is ${n\choose 2}+1$, and for this choice the antecedent "$|E(H)|\ge e(n,r)$" is false for all graphs, so the implication holds vacuously. Minimality follows. $\square$

5) VERIFICATION

• Lemma 600.1 is just unpacking of "minimal such that ..." and is logically correct.
• Lemma 600.2$2$ uses adding an isolated vertex; this preserves "each edge lies in at least one triangle" and preserves per-edge triangle counts.
• Lemma 600.3 matches the computed small cases: e.g., for $n=7$ and $r=6>5=n-2$ the exhaustive search gave $e(7,6)=22={7\choose 2}+1$.
• Computation check: for $n\le 7$ the brute force enumerated all $2^{\binom{n}{2}}$ graphs; the reported $e(n,r)$ values are therefore exact for those $n$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. Exact values of $e(n,r)$ for $n\le 7$ and $r\le 5$ are computed above. In general, $e(n,r)=M(n,r)+1$ (Lemma 600.1), $e$ is nondecreasing in both $n$ and $r$ (Lemma 600.2), and $e(n,r)={n\choose 2}+1$ for $r>n-2$ (Lemma 600.3).

(ii) First gap (crisp). Prove or disprove that for every fixed $r\ge 2$, \[ e(n,r+1)-e(n,r)\to\infty\quad\text{as } n\to\infty, \] or, failing that, produce an explicit infinite sequence of $n$ for which $e(n,r+1)-e(n,r)$ stays bounded.

(iii) Top 3 next moves.

1. Computational: push exact/upper-bound searches to larger $n$ for small $r$ (e.g., $r=2,3,4$) using SAT/ILP rather than brute force, to see whether successive maxima differ by $O(1)$ or grow.
2. Structural: characterize extremal graphs for $M(n,r)$ (all edges in at least one triangle, triangle-multiplicity per edge bounded by $r-1$). Even a coarse structural lemma that such graphs have $o(n^2)$ edges (as stated in the problem) with an explicit quantitative bound could inform the difference/ratio questions.
3. Inequality approach: find two-sided bounds for $M(n,r)$ as a function of $r$ (for fixed $r$), and then compare $M(n,r+1)-M(n,r)$.

(iv) What a minimal counterexample would look like. To refute $e(n,r+1)-e(n,r)\to\infty$ for a fixed $r$, one would need an infinite sequence $n_j\to\infty$ and graphs $H_j$ on $n_j$ vertices with

1. $|E(H_j)|=M(n_j,r+1)$,
2. every edge in at least one triangle,
3. every edge in at most $r$ triangles,

but with $M(n_j,r+1)-M(n_j,r)$ bounded independently of $j$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an edge contained in at least $r$ triangles. Let $r\geq 2$. Is it true that\[e(n,r+1)-e(n,r)\to \infty\] as $n\to \infty$? Is it true that\[\frac{e(n,r+1)}{e(n,r)}\to 1\] as $n\to \infty$? Ruzsa and Szemerédi [RuSz78] proved that $e(n,r)=o(n^2)$ for any fixed $r$.

1) FORMAL RESTATEMENT

Fix integers $n\ge 1$ and $r\ge 2$. For a simple undirected graph $H$ on vertex set $[n]:=\{1,2,\dots,n\}$, write $t_H(e)$ for the number of triangles of $H$ containing the edge $e$.

Define $e(n,r)$ as the minimal integer $E$ such that every graph $H$ on $n$ vertices satisfying

1. $|E(H)|\ge E$, and
2. $t_H(e)\ge 1$ for every edge $e\in E(H)$,

must contain an edge $e$ with $t_H(e)\ge r$.

Edge case: if $r>n-2$, then no edge in any $n$-vertex graph can lie in $r$ triangles (since $t_H(e)\le n-2$). In this case the defining implication can only hold vacuously, and the natural minimal choice is $e(n,r)={n\choose 2}+1$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records: for fixed $r$, $e(n,r)=o(n^2)$ (Ruzsa--Szemerédi). I do not use additional external results.

3) ATTACK PLAN

• Proof-track idea: understand extremal graphs with bounded triangle-multiplicity per edge ($t_H(e)\le r-1$) but with every edge in a triangle ($t_H(e)\ge 1$). Compare the maximum edge counts for successive $r$.
• Disproof-track idea: attempt to build (for fixed $r$) very dense graphs where every edge lies in many triangles but still keep the maximum per edge below $r$, and see whether successive maxima differ by $O(1)$.
• Computation track: brute force for small $n$ to see how $e(n,r)$ behaves.

4) WORK

Fast reality check (exact computation for $n\le 7$). I exhaustively searched all graphs on $n\le 7$ vertices. For each $(n,r)$ I computed \[ M(n,r):=\max\{|E(H)|: H \text{ on } n \text{ vertices, } 1\le t_H(e)\le r-1 \text{ for all edges }e\}, \] and then $e(n,r)=M(n,r)+1$. The exact values found are: \[ \begin{array}{c|cccc} n & e(n,2) & e(n,3) & e(n,4) & e(n,5) \\\hline 3 & 4 & 4 & 4 & 4 \\ 4 & 4 & 7 & 7 & 7 \\ 5 & 7 & 9 & 11 & 11 \\ 6 & 7 & 13 & 13 & 16 \\ 7 & 10 & 16 & 17 & 19 \end{array} \] (For example, $e(7,4)=17$ means there exists a 7-vertex graph with 16 edges, every edge in at least one triangle, and no edge in 4 triangles, but any such graph with 17 edges forces an edge in at least 4 triangles.)

Lemma 600.1 (reformulation as a maximum).
Let \[ M(n,r):=\max\{|E(H)|: H \text{ on } n \text{ vertices, } 1\le t_H(e)\le r-1 \text{ for all edges }e\}. \] Then $e(n,r)=M(n,r)+1$.

Proof. By definition, $e(n,r)$ is the smallest $E$ such that every graph $H$ with $|E(H)|\ge E$ and $t_H(e)\ge 1$ for all edges contains some edge with $t_H(e)\ge r$. Equivalently, $E-1$ is the largest number of edges for which there exists a counterexample graph $H$ with

1. $|E(H)|=E-1$,
2. $t_H(e)\ge 1$ for all edges, and
3. $t_H(e)\le r-1$ for all edges.

That largest value is exactly $M(n,r)$. Hence $e(n,r)=M(n,r)+1$. $\square$

Lemma 600.2 (monotonicity).
For all $n\ge 1$ and $r\ge 2$:

1. $e(n,r+1)\ge e(n,r)$ (nondecreasing in $r$);
2. $e(n+1,r)\ge e(n,r)$ (nondecreasing in $n$).

Proof. $1$ If a graph has an edge in at least $r+1$ triangles, then it has an edge in at least $r$ triangles. Thus any edge threshold that forces an edge in $r+1$ triangles also forces an edge in $r$ triangles, so the minimal threshold for $r+1$ cannot be smaller: $e(n,r+1)\ge e(n,r)$.

$2$ Suppose we had $e(n+1,r)<e(n,r)$. Take an $n$-vertex graph $H$ witnessing that $e(n,r)$ is minimal, i.e., with $|E(H)|=e(n,r)-1$, every edge in at least one triangle, and no edge in $r$ triangles. Add one isolated vertex to form a graph $H'$ on $n+1$ vertices. Then $H'$ still has $|E(H')|=e(n,r)-1$ edges, every edge still lies in a triangle (unchanged), and still no edge lies in $r$ triangles. This contradicts the definition of $e(n+1,r)$ if $e(n+1,r)\le e(n,r)-1$. Hence $e(n+1,r)\ge e(n,r)$. $\square$

Lemma 600.3 (vacuous range $r>n-2$).
If $r>n-2$ then $e(n,r)={n\choose 2}+1$.

Proof. In any graph on $n$ vertices, every edge $e$ can be extended to a triangle by choosing a third vertex, giving at most $n-2$ possibilities. Hence $t_H(e)\le n-2$ always. If $r>n-2$ then the conclusion "there exists an edge contained in at least $r$ triangles" is impossible for every graph $H$. Therefore the defining implication can only hold when the antecedent is false, i.e., when $|E(H)|\ge e(n,r)$ is impossible. The smallest integer larger than the maximum possible number of edges ${n\choose 2}$ is ${n\choose 2}+1$, and for this choice the antecedent "$|E(H)|\ge e(n,r)$" is false for all graphs, so the implication holds vacuously. Minimality follows. $\square$

5) VERIFICATION

• Lemma 600.1 is just unpacking of "minimal such that ..." and is logically correct.
• Lemma 600.2$2$ uses adding an isolated vertex; this preserves "each edge lies in at least one triangle" and preserves per-edge triangle counts.
• Lemma 600.3 matches the computed small cases: e.g., for $n=7$ and $r=6>5=n-2$ the exhaustive search gave $e(7,6)=22={7\choose 2}+1$.
• Computation check: for $n\le 7$ the brute force enumerated all $2^{\binom{n}{2}}$ graphs; the reported $e(n,r)$ values are therefore exact for those $n$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. Exact values of $e(n,r)$ for $n\le 7$ and $r\le 5$ are computed above. In general, $e(n,r)=M(n,r)+1$ (Lemma 600.1), $e$ is nondecreasing in both $n$ and $r$ (Lemma 600.2), and $e(n,r)={n\choose 2}+1$ for $r>n-2$ (Lemma 600.3).

(ii) First gap (crisp). Prove or disprove that for every fixed $r\ge 2$, \[ e(n,r+1)-e(n,r)\to\infty\quad\text{as } n\to\infty, \] or, failing that, produce an explicit infinite sequence of $n$ for which $e(n,r+1)-e(n,r)$ stays bounded.

(iii) Top 3 next moves.

1. Computational: push exact/upper-bound searches to larger $n$ for small $r$ (e.g., $r=2,3,4$) using SAT/ILP rather than brute force, to see whether successive maxima differ by $O(1)$ or grow.
2. Structural: characterize extremal graphs for $M(n,r)$ (all edges in at least one triangle, triangle-multiplicity per edge bounded by $r-1$). Even a coarse structural lemma that such graphs have $o(n^2)$ edges (as stated in the problem) with an explicit quantitative bound could inform the difference/ratio questions.
3. Inequality approach: find two-sided bounds for $M(n,r)$ as a function of $r$ (for fixed $r$), and then compare $M(n,r+1)-M(n,r)$.

(iv) What a minimal counterexample would look like. To refute $e(n,r+1)-e(n,r)\to\infty$ for a fixed $r$, one would need an infinite sequence $n_j\to\infty$ and graphs $H_j$ on $n_j$ vertices with

1. $|E(H_j)|=M(n_j,r+1)$,
2. every edge in at least one triangle,
3. every edge in at most $r$ triangles,

but with $M(n_j,r+1)-M(n_j,r)$ bounded independently of $j$.