Kneser Graphs Are Hamiltonian For n⩾3k

The Kneser graph K(n, k) has as vertices the k-subsets of {1, 2, …, n}. Two vertices are adjacent if the k-subsets are disjoint. In this paper, we prove that K(n, k) is Hamiltonian for n⩾3k, and extend this to the bipartite Kneser graphs.