A graph G is hypohamiltonian if G does not contain a hamiltonian cycle but for any v ∈ V (G) the graph G − v does contain a hamiltonian cycle. Replacing in the preceding sentence “cycle” by “path”, we obtain the definition of a hypotraceable graph.

We call a vertex cubic if it has degree 3, and a graph cubic if all of its vertices are cubic. Consider a graph G. Two edges of G are independent if they have no common vertices. The girth of a graph is the length of its shortest cycle.