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.
References
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).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.