Proof of the Pósa−Seymour Conjecture

In 1974 Paul Seymour conjectured that any graph G of order n and minimum degree at least (k−1)/k · n contains the (k − 1)th power of a Hamiltonian cycle. This conjecture was proved with the help of the Regularity Lemma – Blow-up Lemma method for n ≥ n0 where n0 is very large. Here we present another proof that avoids the use of the Regularity Lemma and thus the resulting n0 is much smaller. The main ingredient is a new kind of connecting lemma.

Joint work with Asif Jamshed.