Higher-dimensional counterexamples to Hamiltonicity

Abstract For $$d \ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , we show that all graphs of d -polytopes have a Hamiltonian line graph if and only if $$d \ne 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≠</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> : 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 3 n vertices in whose line graph any simple path is shorter than $$10 n^{\alpha }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>10</mml:mn> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>α</mml:mi> </mml:msup> </mml:mrow> </mml:math> , for some constant $$\alpha &lt;1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . Moreover, we give four elementary counterexamples of plausible extensions to simplicial complexes of four famous results in Hamiltonian graph theory.