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 (Grünbaum
1974, Thomassen 1974). Thomassen (1974) then showed that there exists a hypotraceable
graph with
vertices for ,
37, 39, 40, and all .
The smallest of these is the 34-vertex Thomassen
graph (left figure above; Thomassen 1974; Bondy and Murty 1976, pp. 239-240).
Walter (1969) gave an example of a connected graph in which the longest paths do not have a vertex in common, a property shared by hypotraceable graphs.
Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin.18, 2001. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy,
J. A. and Murty, U. S. R. Graph
Theory with Applications. New York: North Holland, pp. 61 and 239-240,
1976.Grotschel, M. "On the Monotone Symmetric Travelling Salesman
Problem: Hypohamiltonian/Hypotraceable Graphs and Facets." Math. Operations
Res.5, 285-292, 1980.Grünbaum, B. "Vertices Missed
by Longest Paths or Circuits." J. Combin. Th. A17, 31-38, 1974.Holton,
D. A. and Sheehan, J. The
Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Jooyandeh,
M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.;
and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices."
J. Graph Th.84, 121-133, 2017.Kapoor, S. F.; Kronk,
H. V.; and Lick, D. R. "On Detours in Graphs." Canad. Math.
Bull.11, 195-201, 1968.Thomassen, C. "Hypohamiltonian
and Hypotraceable Graphs." Disc. Math.9, 91-96, 1974.Walter,
H. "Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten
Wege eines Graphen gehen." J. Combin. Th.6, 1-6, 1969.Wiener,
G. and Araya, M. "The Ultimate Question." 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener,
G. and Araya, M. "On Planar Hypotraceable Graphs." J. Graph Th.67,
55-68, 2011.
is a hypotraceable graph if 
has no Hamiltonian path
(i.e., it is not a traceable graph), but 
has a Hamiltonian
path (i.e., is a traceable graph) for every
(Bondy and Murty 1976, p. 61).
vertices for 
,
37, 39, 40, and all 
.
The smallest of these is the 34-vertex Thomassen
graph (left figure above; Thomassen 1974; Bondy and Murty 1976, pp. 239-240).
