  We analyse a polyhedron which contains the convex hull of all Hamiltonian
cycles of a given undirected connected cubic graph. Our constructed polyhedron
is defined by polynomially-many linear constraints in polynomially-many
continuous (relaxed) variables. Clearly, the emptiness of the constructed
polyhedron implies that the graph is non-Hamiltonian. However, whenever a
constructed polyhedron is non-empty, the result is inconclusive. Hence, the
following natural question arises: if we assume that a non-empty polyhedron
implies Hamiltonicity, how frequently is this diagnosis incorrect? We prove
that, in the case of bridge graphs, the constructed polyhedron is always empty.
We also demonstrate that some non-bridge non-Hamiltonian cubic graphs induce
empty polyhedra as well. We compare our approach to the famous
Dantzig-Fulkerson-Johnson relaxation of a TSP, and give empirical evidence
which suggests that the latter is infeasible if and only if our constructed
polyhedron is also empty. By considering special edge cut sets which are
present in most cubic graphs, we describe a heuristic approach, built on our
constructed polyhedron, for which incorrect diagnoses of non-Hamiltonian graphs
as Hamiltonian appear to be very rare. In particular, for cubic graphs
containing up to 18 vertices, only four out of 45,982 undirected connected
cubic graphs were so misdiagnosed. By constrast, we demonstrate that an
equivalent heuristic, when built on the Dantzig-Fulkerson-Johnson relaxation of
a TSP, is mostly unsuccessful in identifying additional non-Hamiltonian graphs.
These empirical results suggest that polynomial algorithms based on our
constructed polyhedron may be able to correctly identify Hamiltonicity of a
cubic graph in all but rare cases.
