The number of triangles is more when they have no common vertex

Xiao, Chuanqi and Katona, Gyula (2021) The number of triangles is more when they have no common vertex. DISCRETE MATHEMATICS, 344 (5). No.-112330. ISSN 0012-365X

Preview	Text 200304450v1.pdf - Submitted Version Download (135kB) | Preview
	Text 1-s2.0-S0012365X21000431-main.pdf - Published Version Restricted to Registered users only Download (402kB) | Request a copy

Abstract

By the theorem of Mantel (1907) it is known that a graph with n vertices and ⌊ n 2 4 ⌋ + 1 edges must contain a triangle. A theorem of Erdős gives a strengthening: there are not only one, but at least ⌊ n 2 ⌋ 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.

Actions (login required)

Edit Item