A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. Graphs that are not traceable are said to be untraceable. The numbers of traceable graphs on n = 1, 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864), where the singleton graph K_1 is conventionally considered traceable. The first few are illustrated above, with a Hamiltonian path indicated in orange for each. Every self-complementary graph is traceable. The following table lists some named graphs that are traceable but not Hamiltonian.

Eulerian cycle | Hamilton-connected graph | Hamiltonian graph | hypotraceable graph | Königsberg bridge problem | unicursal circuit | untraceable graph