An untraceable graph is a graph on at least two vertices that does not possess a Hamiltonian path, i.e., one that is not traceable. The singleton graph is excluded by the convention that it is traceable. All disconnected graphs are therefore untraceable. Untraceable graphs are also known as non-traceable (van Cleemput and Zamfirescu 2018) or nontraceable graphs.
Untraceable graphs are also nonhamiltonian since a graph with no Hamiltonian path cannot contain a Hamiltonian cycle.
A connected bipartite graph with bipartition classes whose sizes differ
by more than 1 is untraceable, since a Hamiltonian
path in a bipartite graph must alternate between
the two bipartition classes. The converse does not hold in general: the E
graph and H graph have equal bipartition sizes but
are untraceable, while the fork graph and spoke
graph 
have bipartition sizes differing by 1 but are untraceable.
Classes of connected graphs that are untraceable include alkane graphs, the members of the banana
tree and firecracker graph families that
are not path graphs, helm
graphs, hypotraceable graphs, Menger
sponge graphs of iteration 
, sunlet graphs, and
web graphs.
Precomputed values are available for a number of named graphs using GraphData[graph, "Untraceable"].
The numbers of nonisomorphic, not-necessarily connected untraceable simple
graphs on 
,
2, ... vertices are 0, 1, 2, 6, 16, 65, 310, 2316,
26241, 522596, ... (OEIS A283420) and the corresponding
numbers of nonisomorphic connected
untraceable graphs are 0, 0, 0, 1, 3, 21, 119, 1087, 12653,
233999, ... (OEIS A283421), the first few of
which are illustrated above.
There are no untraceable polyhedral graphs on 12 or fewer nodes. Examples of small polyhedral untraceable graphs are given in the table below.
