Paperlane

no. 17 · Wednesday 18 November 2026

An extremal question of Erdős et al. on cycles

Zhiyong Gan, Zhiliang Tan and Yi Huang

math.CO · 31 pp

Abstract

This paper addresses an extremal problem on long cycles proposed by Erdős, Faudree, Schelp and Simonovits in 1989. Let \(2\le k\le d<n\) be positive integers. For an n-vertex simple graph G, let \(θ_+^G\) count vertices of degree at least d, and \(C_{\ge k+1}\) denote a cycle of length at least \(k+1\). The original conjecture claimed that G contains a \(C_{\ge k+1}\) whenever \(θ_+^G \ge \lfloor k/2 \rfloor \lfloor (n-1)/d \rfloor+2\). Li, Ma and Ning disproved it with infinite counterexamples and gave linear lower bounds. Gan, Yi and Jiang later obtained piecewise sufficient conditions depending on the parity of k, whose bounds are sharp only when \(k=d\) and loose for \(k\ne d\). We derive a new sufficient condition for \(C_{\ge k+1}\). For odd \(k=d\), we use Woodall's sharp bound \(θ_+^G \ge k(n-2)/(2(k-1))+1\). For all other admissible parameters, our threshold is unified and independent of the parity of k: \(θ_+^G \ge \lfloor k/2 \rfloor (n-1)/d + (n-d-1)\lfloor k/2 \rfloor/(d(d-\lfloor k/2 \rfloor))+1\). We construct \(C_{\ge k+1}\)-free graphs to prove tightness for all admissible k. This resolves this long-standing Erdős-type extremal problem concerning high-degree vertices and long cycles.

comments
31 pages, 2 figures, submitted to Journal of Combinatorial Theory, Series B
fields
Combinatorics
pdf ↗ page arXiv:2611.22824 ↗