Intersecting Set Systems and Hamiltonicity

Abstract: For integers k≥1 and n≥2k+1, the Kneser graph K(n,k) has as vertices all k-element subsets of an n-element ground set, with an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph K(5,2). This problem has received considerable attention in the literature. The main contribution of this paper is to prove the conjecture in full generality.

We also extend this Hamiltonicity result to all connected generalized Johnson graphs J(n,k,s), which have as vertices all k-element subsets of an n-element ground set, with an edge between any two sets whose intersection has size exactly s. In addition, our results apply to Schrijver graphs SG(n,k), the vertex-critical induced subgraphs of Kneser graphs whose vertices correspond to k-element subsets of [n] containing no two consecutive elements.