Open-access mathematical research insights
About Contact
Home / Erdos Problems / Problem #600

Problem #600: Let $e(n,r)$ be minimal such that every graph on $n$...

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...

Problem Statement

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$?
Categories: Graph Theory

Progress

Ruzsa and Szemerédi [RuSz78] proved that $e(n,r)=o(n^2)$ for any fixed $r$.

See also [80].

Source: erdosproblems.com/600 | Last verified: January 15, 2026

Stay Updated

Get weekly digests of new research insights delivered to your inbox.