Problem 574

Is it true that, for $k\geq 2$ ,

\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})=(1+o(1))(n/2)^{1+\frac{1}{k}}.

Source: erdosproblems.com/574

Graph theory
Turán numbers

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The site labels the problem DISPROVED (page last edited 1 April 2026; one comment, no proof claims) and credits two refereed papers: it names [LUW94b] as apparently the first disproof, at $k=3$ and $k=5$ , through bipartite $C_{2k}$ -free graphs with constant $(k-1)/k^{1+1/k}$ , and [FNV06] as an alternative disproof at $k=3$ . Both are accepted claims here, on the refereed venue and the site's acceptance: Lazebnik, Ustimenko and Woldar 1994 and Füredi, Naor and Verstraëte 2006; the problem's standing derives from them.

ErSi82: Erdős, P. and Simonovits, M., Compactness results in extremal graph theory. Combinatorica 2 (1982), no. 3, 275--288; Conjecture 4, p. 278, of which the statement is the case $t=k$ . Library home: Erdős and Simonovits 1982.
FNV06: Füredi, Zoltán and Naor, Assaf and Verstraëte, Jacques, On the Turán number for the hexagon. Adv. Math. 203 (2006), no. 2, 476--496, doi:10.1016/j.aim.2005.04.011, online as an article in press from June 2005 (the site's reference text gives "Adv. Math. (2006), 476-496").
LUW94b: Lazebnik, F. and Ustimenko, V. A. and Woldar, A. J., Properties of certain families of $2k$ -cycle-free graphs. J. Combin. Theory Ser. B 60 (1994), 293--298; doi:10.1006/jctb.1994.1020. The Theorem (p. 295) and the Corollary (p. 297). Library home: Lazebnik, Ustimenko and Woldar 1994; the statements are paged at Lazebnik, Ustimenko and Woldar 1994, Theorem (p. 295) and Lazebnik, Ustimenko and Woldar 1994, Corollary (p. 297).

Problem 574

Status

Proof claims

Discussion