Seymour conjectured that a graph G of order n with minimum vertex degree δ(G)>=k n/(k + 1) contains the kth graph power of a Hamiltonian cycle, generalizing Pósa's Conjecture. Komlós et al. (1998) proved the conjecture for sufficiently large n using Szemerédi's regularity lemma and a technique called the blow-up lemma.

Hajnal-Szemerédi theorem | Hamiltonian cycle | Pósa's conjecture | Pósa's theorem | Szemerédi's regularity lemma