Short proof that Kneser graphs are Hamiltonian for $n\ge 4k$

Abstract

For integers $n\ge k\ge 1$, the Kneser graph $K(n,k)$ is the graph with vertex set $V=[n{]}^{(k)}$ and edge set $E=\{\{x,y\}\in V^{(2)}:x\cap y=\varnothing \}$. Chen proved that for $n\ge 3k$, Kneser graphs are Hamiltonian and later improved this to $n\ge 2.62k+1$. Furthermore, Chen and Füredi gave a short proof that if $k|n$, Kneser graphs are Hamiltonian for $n\ge 3k$. In this note, we present a short proof that does not need the divisibility condition, i.e., we give a short proof that $K(n,k)$ is Hamiltonian for $n\ge 4k$.

3 pages