Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant $c$ such that there is an infinite family of 4-regular 4-connected graphs, each containing exactly $c$ Hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4-regular 3-connected graphs, although it does not hold for planar 4-regular 4-connected graphs by a result of Brinkmann and Van Cleemput [ European J. Combin., 97 (2021), 103395], and that it holds for 4-regular graphs of connectivity 2 with the constant $144 < c$, which we believe to be minimal among all Hamiltonian 4-regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every nonnegative integer $k$ there is a 5-regular graph on $26 + 6k$ vertices with $2^{k+10} \cdot 3^{k+3}$ Hamiltonian cycles. We prove that for every $d \ge 3$ there is an infinite family of Hamiltonian 3-connected graphs with minimum degree $d$, with a bounded number of Hamiltonian cycles. It is shown that if a 3-regular graph $G$ has a unique longest cycle $C$, at least two components of $G - E(C)$ have an odd number of vertices on $C$, and that there exist 3-regular graphs with exactly two such components.

A spider is a tree with at most one branch (a vertex of degree at least 3) centred at the branch if it exists, and centred at any vertex otherwise. A graph G is arachnoid if for any vertex v of G, there exists a spanning spider of G centred at v—in other words: there are spiders everywhere! Hypotraceable graphs are non-traceable graphs in which all vertex-deleted subgraphs are traceable. Gargano et al. (2004) defined arachnoid graphs as natural generalisations of traceable graphs and asked for the existence of arachnoid graphs that are (i) non-traceable and non-hypotraceable, or (ii) in which some vertex is the centre of only spiders with more than three legs. An affirmative answer to (ii) implies an affirmative answer to (i). While non-traceable, non-hypotraceable arachnoid graphs were described in Wiener (2017), (ii) remained open. In this paper we give an affirmative answer to this question and discuss spanning spiders whose legs must have some minimum length.

Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both dealing with non-Hamiltonian $n$-vertex graphs and their $(n-2)$-cycles, we investigate $K_2$- Hamiltonian graphs, i.e., graphs in which the removal of any pair of adjacent vertices yields a Hamiltonian graph. In this first part, we prove structural properties and show that there exist infinitely many cubic non-Hamiltonian $K_2$-Hamiltonian graphs, both of the 3-edge-colorable and the non-3-edge-colorable variety. In fact, cubic $K_2$-Hamiltonian graphs with chromatic index 4 (such as Petersen's graph) are a subset of the critical snarks. On the other hand, it is proven that non-Hamiltonian $K_2$-Hamiltonian graphs of any maximum degree exist. Several operations conserving $K_2$-Hamiltonicity are described, one of which leads to the result that there exists an infinite family of non-Hamiltonian $K_2$-Hamiltonian graphs in which, asymptotically, a quarter of vertices has the property that removing such a vertex yields a non-Hamiltonian graph. We extend a celebrated result of Tutte by showing that every planar $K_2$-Hamiltonian graph with minimum degree at least 4 is Hamiltonian. Finally, we investigate $K_2$-traceable graphs and discuss open problems.

In this note, we consider triangulations of the plane. Ozeki and the second author asked whether there are non-hamiltonian 1-tough triangulations in which every two separating triangles are disjoint. We answer this question in the affirmative and strengthen a result of Nishizeki by proving that there are infinitely many non-hamiltonian 1-tough triangulations with pairwise disjoint separating triangles.

A seminal theorem of Tutte states that 4-connected planar graphs are Hamiltonian. Applying a result of Thomas and Yu, one can show that every 4-connected graph with crossing number 1 is Hamiltonian. In this paper, we continue along this path and prove the titular statement. We also discuss the traceability and Hamiltonicity of 3-connected graphs with small crossing number and few 3-cuts, and present applications of our results.