Erdős Problem #574

Erdős Problem 574

Statement and result.

A bipartite graph without four- or six-cycles.

Two distinct points on a common line have different first coordinates: $1$ determines $y,z$ once $x$ and the line are given. For points with different first coordinates, the first equation uniquely determines the slope $t$, and then $b,c$ are determined. Thus two points have at most one common line, excluding $C_4$.

Suppose a six-cycle exists. Write its point vertices as $P_1,P_2,P_3$, with first coordinates $x_1,x_2,x_3$; these are pairwise distinct. Let $t_i$ be the slope of the line joining $P_i$ and $P_{i+1}$, with indices cyclic. Subtracting $1$ and summing gives \[ \sum_{i=1}^3 t_i(x_{i+1}-x_i)=0, \qquad \sum_{i=1}^3 t_i(x_{i+1}^2-x_i^2)=0. \tag{2} \] The two coefficient rows are independent: their coordinate ratios are $x_i+x_{i+1}$, which are pairwise distinct. Their common kernel has dimension one and contains $(1,1,1)$. Therefore $t_1=t_2=t_3$. At a fixed point, $1$ determines a unique line of a given slope. The three line vertices must consequently be the same, contradicting a six-cycle. This proves both exclusions over every field used here.

Duplicating just one class.

Such a cycle would use three distinct points and three distinct line copies. If the underlying line labels were all different, their projection would be a six-cycle in the original graph. If two labels were equal, that underlying line would contain all three point vertices: two of the three successive point pairs occur on it. The third underlying line would then share two distinct points with the first. The already proved absence of $C_4$ forces it to have the same label as well. But this would require three distinct copies of one line, whereas only two were provided. Both possibilities are impossible.

Strict violation of the proposed constant.

Attribution and scope.

Completion rate estimate: 100%.

1) FORMAL RESTATEMENT

Fix an integer $k\ge 2$. Let $C_\ell$ denote the cycle of length $\ell$. Define $\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})$ as the maximum number of edges in an $n$-vertex simple graph containing no cycle of length $2k-1$ and no cycle of length $2k$.

The question is whether \[ \mathrm{ex}(n;\{C_{2k-1},C_{2k}\}) = (1+o(1))(n/2)^{1+1/k} \quad\text{as }n\to\infty. \] Equivalently, whether \[ \frac{\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})}{n^{1+1/k}}\to 2^{-(1+1/k)}. \]

2) QUICK LITERATURE/CONTEXT CHECK

The source file states this as a problem of Erdős and Simonovits, and points to #573 as the case $k=2$. The Erdős Problems website still lists #574 as open as of the access date shown there $2025-11-19$.

3) ATTACK PLAN

Proof-track ideas: - Show an upper bound $O(n^{1+1/k})$ by controlling the number of length-$2k$ cycles forced by high average degree, and then use forbidding $C_{2k-1}$ to force near-bipartiteness. - Try to reduce to the "bipartite $C_{2k}$" extremal problem by proving a stability/regularity statement.

Construction-track ideas: - Take bipartite graphs with many edges and no $C_{2k}$ (then automatically no $C_{2k-1}$), aiming for the constant $2^{-(1+1/k)}$. - Try to beat the bipartite constant by adding odd-cycle structure that still avoids $C_{2k-1}$.

I establish two basic structural lemmas and compute tiny cases for $k=3$; no asymptotic resolution follows.

4) WORK

FAST REALITY CHECK (exact brute force for $k=3$, forbidding $C_5$ and $C_6$). Exact maxima for graphs with no $C_5$ and no $C_6$ for $n\le 7$ (labeled enumeration): \[ \mathrm{ex}(3;\{C_5,C_6\})=3,\ \mathrm{ex}(4;\{C_5,C_6\})=6,\ \mathrm{ex}(5;\{C_5,C_6\})=7,\ \mathrm{ex}(6;\{C_5,C_6\})=9,\ \mathrm{ex}(7;\{C_5,C_6\})=12. \] (For $n<5$ the $C_5,C_6$ constraints are vacuous.)

Lemma 574.1 (neighborhood cycle lifting). Let $G$ be a graph and $v\in V(G)$. If the induced subgraph $G[N(v)]$ contains a cycle $C_\ell$, then $G$ contains a cycle $C_{\ell+1}$.

In particular, if $G$ is $\{C_{2k-1},C_{2k}\}$-free, then for every vertex $v$, \[ G[N(v)]\text{ is }\{C_{2k-2},C_{2k-1}\}\text{-free}. \] Proof. Suppose $G[N(v)]$ contains a cycle with vertex sequence $u_1-u_2-\cdots-u_\ell-u_1$. By definition of $N(v)$, each $u_i$ is adjacent to $v$. Then in $G$ the vertices \[ v,u_1,u_2,\dots,u_\ell \] form the cycle \[ v-u_1-u_2-\cdots-u_\ell-v, \] which has length $\ell+1$. Therefore presence of $C_{2k-2}$ in $G[N(v)]$ would create $C_{2k-1}$ in $G$, and presence of $C_{2k-1}$ in $G[N(v)]$ would create $C_{2k}$ in $G$. $\square$

Lemma 574.2 (bipartite reduction gives a universal lower bound). Let $k\ge 2$. If $H$ is a bipartite graph with no $C_{2k}$, then $H$ is automatically $\{C_{2k-1},C_{2k}\}$-free. Consequently, \[ \mathrm{ex}(n;\{C_{2k-1},C_{2k}\})\ge \mathrm{ex}_{\mathrm{bip}}(n;C_{2k}), \] where $\mathrm{ex}_{\mathrm{bip}}(n;C_{2k})$ denotes the maximum number of edges in an $n$-vertex bipartite $C_{2k}$-free graph. Proof. A bipartite graph contains no odd cycle of any length, so in particular it contains no $C_{2k-1}$. If it is also $C_{2k}$-free, then it contains neither $C_{2k-1}$ nor $C_{2k}$. The inequality follows because the class of bipartite $C_{2k}$-free graphs on $n$ vertices is a subclass of all $\{C_{2k-1},C_{2k}\}$-free graphs on $n$ vertices. $\square$

What these lemmas do (and do not) give. Lemma 574.1 provides a recursive obstruction: a very dense neighborhood would force a forbidden long cycle. Lemma 574.2 shows that any good bipartite $C_{2k}$-free construction is also a construction for this problem. However, neither lemma alone yields the conjectured constant $2^{-(1+1/k)}$ nor an upper bound of order $n^{1+1/k}$ without additional input.

5) VERIFICATION

- Lemma 574.1: the constructed $C_{\ell+1}$ is a simple cycle because the $u_i$ are distinct in $C_\ell$ and none equals $v$. - Lemma 574.2: uses only the definition of bipartite (no odd cycles) and the subgraph notion. - The small-$n$ computations for $k=3$ were checked by exhaustive enumeration of all labeled graphs on $n\le 7$ vertices and direct cycle detection for lengths 5 and 6.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result: For any fixed $k\ge 2$, forbidding $C_{2k-1}$ and $C_{2k}$ implies the neighborhood recursion of Lemma 574.1, and there is always the bipartite lower bound of Lemma 574.2.

(ii) First gap (crisp): Prove an upper bound of the correct order, e.g. show $\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})=O_k(n^{1+1/k})$.

(iii) Top 3 next moves (concrete): 1. Prove (or find a counterexample to) a stability statement: any near-extremal $\{C_{2k-1},C_{2k}\}$-free graph must be close to bipartite. 2. Use Lemma 574.1 to bound $\sum_v e(G[N(v)])$ and relate it to the total number of short cycles / walks; attempt to force a $C_{2k}$ when $e(G)$ is too large. 3. Computation for fixed $k$ (say $k=3,4$): exact optimization for $n=8,9,10$ to guess extremal examples and test whether the extremal graphs appear bipartite.

(iv) Minimal counterexample structure: A disproof would require fixed $k$ and an infinite sequence of graphs $G_n$ with no $C_{2k-1}$ and no $C_{2k}$ but $e(G_n)\ge (1+\varepsilon)(n/2)^{1+1/k}$. Such a family would have to exploit the freedom to contain many shorter cycles (including $C_3$ and $C_4$) while carefully avoiding just the two consecutive lengths $2k-1,2k$.