is not Hamiltonian, but it was long conjectured that this was the sole exception and that every other connected Kneser graph is Hamiltonian.

In 2003, Ya-Chen Chen showed that the Kneser graph contains a Hamiltonian cycle if
:Since
:holds for all , this condition is satisfied if
:Around the same time, Shields showed (computationally) that, except the Petersen graph, all connected Kneser graphs with are Hamiltonian.

In 2021,

1.Previous
3.Next