Given a simple polytope, that is a polytope such that each vertex is adjacent to exactly 3 other vertices. Does there exist a cycle along its edges visiting every vertex precisely once? In general, the answer to this question is no, however, for some polytopes, for instance the cube, there does exist such a cycle.
Barnette's conjecture states that if a simple polytope has only even-sided faces, such a cycle will always exist. Over time, this conjecture has become one of the most famous problems in graph theory. Despite being of purely combinatorial interest, Barnette's conjecture is also closely connected to optimisation problems and the P-NP-problem.
In 1975, Goodey verified the conjecture for all polytopes with faces of size up to 6 (for example the cube or the truncated octahedron).
We substantially strengthen Goodey's result by proving the conjecture for all polytopes with faces of size up to 8 (e.g. the great rhombicuboctahedron). Parts of the proof are computational, including a distinction of 339.068.624 cases.