Extremal conjecture for equal-degree endpoint paths of odd length

From papers

Let p(N)p_{\ell}(N) denote the maximum number of edges in a graph on NN vertices containing no path of length \ell whose endpoints have equal degree. For odd integers 3\ell\geq 3 and sufficiently large positive integers nn, consider graphs on 2n+12n+1 vertices; the complete bipartite graph Kn,n+1K_{n,n+1} has n2+nn^2+n edges.

Odd-length extremal conjecture. For any odd integer 3\ell\geq 3 and sufficiently large nn, it holds that

p(2n+1)=n2+n.p_{\ell}(2n+1)=n^2+n.

Equivalently, Kn,n+1K_{n,n+1} remains extremal for paths of every odd length at least three. This extends the problem of Erdős and Hajnal on paths with equal-degree endpoints; the asserted extremality is posed as an open problem for general odd lengths.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Kaizhe Chen and Jie Ma, “A problem of Erdős and Hajnal on paths with equal-degree endpoints”, arXiv:2503.19569 (2025).

Solutions 0

No solutions have been posted yet.