Many edges are contained in \(5\)cycles
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
Problem[1]
Suppose a graph \(G\) contains \(\lfloor n^2/4 \rfloor\) edges. Is it true that there are at least \(2n^2/9\) edges each of which occur in a pentagon in \(G\)?In [1], Erdös stated that in every graph on \( n\) vertices and \( \lfloor n^2/4 \rfloor\) edges, there are at least \( 2n^2/9\) edges, each of which occur in an odd cycle and this is best possible. He said, "Perhaps there are at least \( 2n^2/9\) edges which occur in a pentagon. This would follow if we could prove that every graph on \( n\) vertices and \( \lfloor n^2/4 \rfloor\) edges contains a triangle for which there are \( n/2O(1)\) vertices which are joined to at least two vertices of our triangle." Erdös and Faudree observed that every graph on \( 2n\) edges and \( n^2+1\) edges has a triangle whose vertices are joined to at least \( n+2\) vertices and this is best possible.
Bibliography  

1  P. Erdös. Some recent problems and results in graph theory. Discrete Math. 164 (1997), 8185.
