Higher-dimensional counterexamples to Hamiltonicity

Abstract

For $d\ge 2$, we show that all graphs of $d$-polytopes have a Hamiltonian line graph if and only if $d\ne 3$: We exhibit a graph of a $3$-polytope on $252$ vertices whose line graph does not even have Hamiltonian paths. Adapting a construction by Grünbaum and Motzkin, for large $n$ we also construct simple $3$-polytopes on $3n$ vertices in whose line graph any simple path is shorter than $10n^{\hat{I}}\pm$, for some constant $\hat{I}\pm <1$. Moreover, we give four elementary counterexamples of plausible extensions to simplicial complexes of four famous results in Hamiltonian graph theory.