Every 4-connected \{claw, hourglass\}-free graph is 2-Hamiltonian (Q7231827)

For an integer \(s\ge0\), a graph \(G(V,E)\) is \(s\)-Hamiltonian if, for any \(s\)-subset \(X\subseteq V\), \(G-X\) is Hamiltonian; an alternative definition is discussed in \S2 of the paper. \(\Gamma\), the hourglass, is the unique 5-vertex graph with degree sequence \(4,2,2,2,2\) -- this is the graph the authors called \(\Gamma_0\) in their paper (jointly with other authors) [\textit{A. Kabela} et al., Discrete Math. 348, No. 2, Article ID 114305, 19 p. (2025; Zbl 1553.05100)]; the claw is \(K_{1,3}\). \(G\) is \(\{K_{1,3},\Gamma\}\)-free if it contains neither of the two ``forbidden'' subgraphs as an induced subgraph. The main result of this paper is Theorem 1: Let \(s\ge2\) be an integer, and let \(G\) be an \((s+2)\)-connected \(\{K_{1,3},\Gamma\}\)-free graph. Then \(G\) is \(s\)-Hamiltonian. This theorem is proved by induction on \(s\), beginning with the titular theorem, Theorem 2, which is the case \(s=2\). A consequence of Theorem 1 is Corollary 3: (i) Let \(s\ge2\) be an integer, and let \(G\) be a \(\left\{K_{1,3},\Gamma\right\}\)-free graph. Then \(G\) is \(s\)-Hamiltonian if and only if \(G\) is \((s+2)\)-connected. (ii) For an integer \(s\ge2\), \(s\)-Hamiltonicity is polynomial-time decidable in the class of \(\{K_{1,3},\Gamma\}\)-free graphs.