The longest cycles in a graph G with minimum degree at least ∣G∣k

AbstractN. Alon [J. Graph Theory 10 (1986), 123–127] proved that if the minimum degree of a graph G is not less than ⌈∣V(G)∣k⌉, then the circumference of G is at least ⌊∣V(G)∣(k − 1)⌋. In this article, we show a stronger theorem: if dG(x) + dG(y) ≥ ⌈2∣V(G)∣k⌉ for any nonadjacent distinct vertices x and y of V(G), then G has a cycle of length at least ⌈∣V(G)∣(k − 1)⌉. (The lower bound ⌈∣V(G)∣(k − 1)⌉ is sharp.