Four-cycles in graphs without a given even cycle
Daniela Kühn, Deryk Osthus · Journal of Graph Theory · 2004
We prove that every bipartite C2l-free graph G contains a C4-free subgraph H with e(H) ≥ e(G)/(l – 1). The factor 1/(l – 1) is best possible. This implies that ex(n, C2l) ≤ 2(l – 1)ex(n, {C4, C2l}), which settles a special case of a conjecture of Erdős and Simonovits. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 147–156, 2005