2020/03/09 by Chuanqi Xiao, Xiao, Chuanqi, Gyula O. H. Katona +1 · 1 citation
Mathematics · #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #History and Theory of Mathematics #Mathematics and Applications
paper · doi:10.48550/arxiv.2003.04450
openalex publication_date 2020/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By the theorem of Mantel [5] it is known that a graph with n vertices and \lfloor \fracn24 \rfloor+1 edges must contain a triangle. A theorem of Erdős gives a strengthening: there are not only one, but at least \lfloor(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.