Erdős's conjecture on extremal odd-cycle edges
Erdős's conjecture on extremal odd-cycle edges
Let be an -vertex graph with edges, and let a -edge mean an edge contained in a cycle of length . Assume that , , and , where is the threshold in the conjecture. Erdős's conjecture on extremal odd-cycle edges. If has the minimum number of -edges among all -vertex graphs with edges, then is connected and has two blocks, one of which is a complete bipartite graph and the other of which is almost complete. The statement is presented as a corrected version of Erdős's conjecture. The surrounding discussion records asymptotic results on odd-cycle edges, but does not resolve this structural assertion.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Zoltán Füredi and Zeinab Maleki, “The minimum number of triangular edges and a symmetrization method for multiple graphs”, arXiv:1411.0771 (2016).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.