PROVED
This has been solved in the affirmative.
Is it true that, for every $c>0$, there exists $f(c)$ such that every graph on $n$ vertices with at least $\lfloor n^2/4\rfloor+k$ edges, where $k<c n$, contains at least $k-f(c)$ many edge disjoint triangles?
Erdős proved this for $c<1/2$ using a theorem of Erdős and Gallai, which says that every graph on $n$ vertices with at least $(n-1)^2/4+2$ many edges, with chromatic number $3$, must contain a triangle.
In fact, Erdős proved this is true with $f(c)=0$ for $c<1/2$. At first Erdős thought $f(c)=0$ for larger values of $c$ but this is false: an example of Sauer proves that $f(2)\geq 1$.
Sauer gave an example of a graph on $n$ vertices with $\lfloor n^2/4\rfloor+2n-6$ many edges which contains only $2n-7$ many edge disjoint triangles: if $n=2r+4$ then $G$ is the complete tripartite graph on $[r]\times [r]\times [4]$, with a $K_4$ on the $[4]$ vertices also.
This is true, and was proved by Györi
[Gy88] who proved that this is true with $f(c)\ll c^2$, and also that $f(c)=0$ if $c<2$ for odd $n$ or $c<3/2$ for even $n$.
View the LaTeX source
This page was last edited 31 October 2025. View history
Additional thanks to: Stijn Cambie
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1009, https://www.erdosproblems.com/1009, accessed 2026-04-11
