TOPICS

# Untraceable Graph

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.

Hamiltonian Path, Nonhamiltonian Graph, Traceable Graph

## References

Sloane, N. J. A. Sequences A283420 and A283421 in "The On-Line Encyclopedia of Integer Sequences."van Cleemput, N. and Zamfirescu, C. T. "Regular Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput. 338 192-206, 2018.

## Cite this as:

Weisstein, Eric W. "Untraceable Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UntraceableGraph.html