Odd Graphs Are Prism-Hamiltonian and Have a Long Cycle.

The odd graph <italic>O</italic>_{<italic>k</italic>} is the graph whose vertices are all subsets with <italic>k</italic> elements of a set {1,…,2<italic>k</italic> + 1}, and two vertices are joined by an edge if the corresponding pair of <italic>k</italic>-subsets is disjoint. A conjecture due to Biggs claims that <italic>O</italic>_{<italic>k</italic>} is hamiltonian for <italic>k</italic> ≥ 3 and a conjecture due to Lovász implies that <italic>O</italic>_{<italic>k</italic>} has a hamiltonian path for <italic>k</italic> ≥ 1. In this paper, we show that the prism over <italic>O</italic>_{<italic>k</italic>} is hamiltonian and that <italic>O</italic>_{<italic>k</italic>} has a cycle with .625|<italic>V</italic>(<italic>O</italic>_{<italic>k</italic>})| vertices at least. [ABSTRACT FROM AUTHOR]