An untraceable graph is a graph that does not possess a Hamiltonian path, i.e., one that is not 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.
Classes of connected graphs that are untraceable include alkane graphs, banana trees, firecracker graphs, helm graphs, hypotraceable graphs, Menger sponge graphs, sunlet graphs, and web graphs.
Precomputed values are available for a number of named graphs using GraphData[graph, "Untraceable"].
The numbers of not-necessarily connected untraceable simple graphs on 
, 2, ... nodes are 0, 1, 2, 6, 16, 65, 310, 2316, 26241,
522596, ... (OEIS A283420) and the corresponding
numbers of 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 of fewer nodes. Examples of small polyhedral untraceable graphs are given in the table below.
