Bipartite Kneser graphs are Hamiltonian

Torsten Mütze, Pascal Su

Published 2015-03-31Version 1

The Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $[n]:=\{1,2,\ldots,n\}$ and an edge between any two vertices (=sets) that are disjoint. The bipartite Kneser graph $H(n,k)$ has as vertices all $k$-element and $(n-k)$-element subsets of $[n]$ and an edge between any two vertices where one is a subset of the other. It has long been conjectured that all connected Kneser graphs and bipartite Kneser graphs (apart from few trivial exceptions) have a Hamilton cycle. The main contribution of this paper is proving this conjecture for bipartite Kneser graphs. We also establish the existence of long cycles in Kneser graphs (visiting almost all vertices), generalizing and improving upon previous results on this problem.