Erdős's conjecture on extremal odd-cycle edges

About 12 years old · traced to

Let GG be an nn-vertex graph with ee edges, and let a C2k+1C_{2k+1}-edge mean an edge contained in a cycle of length 2k+12k+1. Assume that e>n2/4e>n^2/4, k≥3k\geq 3, and n>nkn>n_k, where nkn_k is the threshold in the conjecture. Erdős's conjecture on extremal odd-cycle edges. If GG has the minimum number of C2k+1C_{2k+1}-edges among all nn-vertex graphs with ee edges, then GG 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

Never refreshed

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.