A Hamiltonian graph is a graph that contains a cycle passing through every single vertex exactly once (called a Hamiltonian cycle). A natural follow-up question is whether such a graph must also contain cycles of lengths close to the maximum. Specifically, if a graph has n vertices and is Hamiltonian, does it have to contain a cycle of length n-1, or n-2, or other lengths just slightly shorter than n? This question becomes more interesting when you also require that every vertex has many connections, measured by the minimum degree.
In 1984, mathematician Roland Haggkvist asked whether you could build a Hamiltonian graph where every vertex has at least 3 connections but where no cycle comes close to visiting all vertices, specifically no cycle of length n-2 exists. He admitted he could not find any such example. This paper resolves that 40-year-old open problem with a clear answer: yes, such graphs exist, and the authors explicitly construct them. Their first result shows that for any minimum degree d of at least 3, and for sufficiently large n, there is a Hamiltonian graph on n vertices with minimum degree d that completely avoids any cycle of length n-2.
The authors go much further than just answering Haggkvist's original question. Their second result shows that you can simultaneously avoid all cycle lengths in a wide range near the top, not just n-2 but also n-3, n-4, and so on, up to any fixed number of lengths below n, all while keeping the graph Hamiltonian and maintaining a high minimum degree. The constructions are explicit and combinatorial, meaning the authors actually build the graphs rather than just proving they exist abstractly. The paper closes by posing several new open problems, suggesting that the relationship between Hamiltonicity, minimum degree, and near-spanning cycle lengths still has much left to explore.