Distributing pairs of vertices on Hamiltonian cycles

Let G be a graph of order n with minimum degree \(\delta (G) \geqslant \tfrac{n}{2} + 1\). Faudree and Li (2012) conjectured that for any pair of vertices x and y in G and any integer \(2 \leqslant k \leqslant \tfrac{n}{2}\), there exists a Hamiltonian cycle C such that the distance between x and y on C is k. In this paper, we prove that this conjecture is true for graphs of sufficiently large order. The main tools of our proof are the Regularity lemma of Szemerédi and the Blow-up lemma of Komlós et al. (1997).