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/2-O(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), 81-85.
|