Extremal problems of Erdős, Faudree, Schelp and Simonovits on paths and cycles

Abstract For positive integers n > d ≥ k , let ϕ ( n , d , k ) denote the least integer ϕ such that every n-vertex graph with at least ϕ vertices of degree at least d contains a path on k + 1 vertices. Many years ago, Erdős, Faudree, Schelp and Simonovits proposed the study of the function ϕ ( n , d , k ) , and conjectured that for any positive integers n > d ≥ k , it holds that ϕ ( n , d , k ) ≤ ⌊ k − 1 2 ⌋ ⌊ n d + 1 ⌋ + ϵ , where ϵ = 1 if k is odd and ϵ = 2 otherwise. In this paper we determine the values of the function ϕ ( n , d , k ) exactly. This confirms the above conjecture of Erdős et al. for all positive integers k ≠ 4 and in a corrected form for the case k = 4 . Our proof utilizes, among others, a lemma of Erdős et al. [3] , a theorem of Jackson [6] , and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin [7] , where the latter two results concern maximum cycles in bipartite graphs . Moreover, we construct examples to provide answers to two closely related questions raised by Erdős et al.