A graph G is a hypotraceable graph if G has no Hamiltonian path (i.e., it is not a traceable graph), but G - v has a Hamiltonian path (i.e., is a traceable graph) for every v element V. There are no hypotraceable graphs on ten or fewer nodes (E. Weisstein, Dec. 11, 2013). In fact, the nonexistence of hypotraceable graphs on small numbers of vertices led T. Gallai to conjecture that no such graphs exist. This conjecture was refuted when a hypotraceable graph with 40 vertices was subsequently found by Horton. Thomassen then showed that there exists a hypotraceable graph with p vertices for p = 34, 37, 39, 40, and all p>=42. The smallest of these is the 34-vertex Thomassen graph (left figure above; Thomassen 1974, pp. 239-240).

Hamilton-connected graph | hypohamiltonian graph | planar hypotraceable graph | Thomassen graphs | traceable graph | Wiener-Araya graph | Zamfirescu graphs