By the theorem of Mantel $[5]$ it is known that a graph with $n$ vertices and $lfloor frac{n^{2}}{4} rfloor+1$ edges must contain a triangle. A theorem of ErdH{o}s gives a strengthening: there are not only one, but at least $lfloorfrac{n}{2}rfloor$ triangles. We give a further improvement: if there is no vertex contained by all triangles then there are at least $n-2$ of them. There are some natural generalizations when $(a)$ complete graphs are considered (rather than triangles), $(b)$ the graph has $t$ extra edges (not only one) or $(c)$ it is supposed that there are no $s$ vertices such that every triangle contains one of them. We were not able to prove these generalizations, they are posed as conjectures.
Download