---
tag: 45DZ4F1T9N
kind: statement
role: proposition
name: Pósa-Seymour Conjecture
sources:
  - wikipedia: en:69392163@r1338146833
    locator: Blow-up lemma, section Applications > Pósa-Seymour Conjecture
    note: adopted
    mention: wikipedia://en/69392163#INWZ
    sections: [Statement]
inventory: [D6V2QMEYAP]
---

## Statement

In 1962, Lajos Pósa conjectured that every $n$-vertex graph with minimum degree at least $\frac{2n}3$ contains the square of a Hamiltonian cycle, generalizing Dirac's theorem. The conjecture was further extended by Paul Seymour in 1974 to the following:

Every graph on $n$ vertices with minimum degree at least $\frac{kn}{k+1}$ contains the $k$-th power of a Hamiltonian cycle.

The blow-up lemma was used by Komlós, Sárközy, and Szemerédi to prove the conjecture for all sufficiently large values of $n$ (for a fixed $k$) in 1998.