Frontiers in Mathematical Sciences

On Erdős' Conjecture on Pentagonal Edges and Other Type of Edges

Zeinab Maleki
Isfahan University of Technology


Erdős, Faudree, and Rousseau (1992) showed that a graph on $n$ vertices and at least $\lfloor n^2/4\rfloor + 1$ edges has at least $2\lfloor n/2\rfloor + 1$ edges in triangles. To see that this result is sharp, consider the graph obtained by adding one edge to the larger side of the complete bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2\rfloor}$. In this talk, we give an asymptotic formula for $h(n, e, K_3)$, the minimum number of edges contained in triangles in a graph having $n$ vertices and $e$ edges, where $e > n^2/4$ arbitrary. The main tool of the proof is a generalization of Zykov's symmetrization method that can be applied for several graphs simultaneously. We apply our weighted symmetrization method to tackle Erdős' conjecture concerning the minimum number of edges on $5$-cycles. We further extend our results to give an asymptotic formula for $h(n, e, F)$, the minimum number of $F$-edges in an $(n, e)$-graph when $n \rightarrow \infty$ and $F$ is a given $3$-chromatic graph. This is a joint work with Zóltan Füredi.