Pósa–Seymour conjecture for powers of Hamilton cycles

The conjecture asks whether the minimum-degree condition forces the corresponding power of a Hamilton cycle. Pósa proposed the square case in 1962; the general conjecture was proved only asymptotically by Komlós, Sárközy, and Szemerédi.

Known results

• For every fixed $k$, sufficiently large graphs with $\delta(G)\geq \frac{k}{k+1}n$ contain the $k$th power of a Hamilton cycle (Komlós, Sárközy, and Szemerédi, 1996–1997).
• The square case has an explicit sufficient bound: $n\geq 2\times 10^8$ and $\delta(G)\geq \frac{2}{3}n$ suffice; the unrestricted finite case remains open.
• Later surveys record alternative proofs and improved bounds, but not a complete finite resolution.

Current status (as of September 2026): the asymptotic theorem is settled, while the finite Pósa–Seymour conjecture, including unresolved small orders, remains open; no newer proof or counterexample was found.