Traceable Graph

A traceable graph is a graph that possesses a Hamiltonian path, with the singleton graph also considered traceable by convention. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. Graphs that are not traceable are said to be untraceable.

For a bipartite graph with bipartition classes and , traceability requires , since a Hamiltonian path must alternate between the two classes. Thus a connected bipartite graph whose bipartition sizes differ by more than 1 is untraceable. 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.

Traceability also requires , where is the floor function, is the matching number and is the vertex count, since every other edge of a Hamiltonian path gives a matching of this size.

The numbers of nonisomorphic traceable simple graphs on , 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864). The first few are illustrated above, with a Hamiltonian path indicated in orange for each.

Every finite self-complementary graph is traceable (Clapham 1974, Camion 1975; Farrugia 1999, p. 52).

The Lovász conjecture states that without exception, every connected vertex-transitive graph is traceable.

Every finite rectangular grid graph with positive integer side lengths is traceable. For a grid with at least two vertices, a Hamiltonian path can be constructed recursively by traversing successive layers in alternating forward and reverse order, joining their corresponding endpoints.

The following table lists some named graphs that are traceable but not Hamiltonian.

graph
theta-0 graph	7
Petersen graph	10
Herschel graph	11
Blanuša snarks	18
flower snark	20
Coxeter graph	28
double star snark	30
Tutte graph	46
Szekeres snark	50