Polyhedra with few 3-cuts are Hamiltonian (Q1732035)

Summary: In 1956, Tutte showed that every planar 4-connected graph is Hamiltonian. In this article, we will generalize this result and prove that polyhedra with at most three \(3\)-cuts are Hamiltonian. In [J. Graph Theory 41, No. 2, 138--150 (2002; Zbl 1012.05106)], \textit{B. Jackson} and \textit{X. Yu} have shown this result for the subclass of triangulations. We also prove that polyhedra with at most four \(3\)-cuts have a Hamiltonian path. It is well known that for each \(k\geq 6\) non-Hamiltonian polyhedra with \(k\) \(3\)-cuts exist. We give computational results on lower bounds on the order of a possible non-Hamiltonian polyhedron for the remaining open cases of polyhedra with four or five \(3\)-cuts.