There are several definitions of "almost Hamiltonian" in use.

As defined by Punnim et al. (2007), an almost Hamiltonian graph is a graph on
nodes having Hamiltonian number .

As defined by Sanders (1987), a graph with vertices is almost Hamiltonian if every subset of vertices is contained in a circuit, a definition which is
similar to that for a maximally nonhamiltonian
graph.

This work adopts the definition of Punnim et al. (2007). The numbers of almost Hamiltonian graphs of this type on , 2, ... vertices are 0, 0, 1, 1, 7, 28, 257, 2933, ... (OEIS
A185360), the first few of which are illustrated
above.

Since a tree has Hamiltonian number ,
an almost Hamiltonian tree satisfies , giving . Since the 3-path graph
is the only tree on three nodes, it is also the only almost
Hamiltonian tree.

Punnim et al. (2007) proved that there exists an almost Hamiltonian cubic graph for every even order . The Petersen graph
is the unique almost Hamiltonian cubic graph on 10 vertices, and Tietze's
graph is the unique almost Hamiltonian cubic graph on 12 vertices (Punnim et
al. 2007). Punnim et al. (2007) proved that a cubic nonhamiltonian graph
on
vertices is almost Hamiltonian iff it is 2-connected and
contains a cycle of length . Examples of 2-connected cubic nonhamiltonian graphs on
vertices lacking a -cycle and therefore not almost Hamiltonian are summarized
in the following table.

Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security7,
83-86, 2007.Sanders, J. H. "Circuit Preserving Edge Maps II."
J. Combin. Th., Ser. B42, 146-155, 1987.Sloane, N. J. A.
Sequence A185360 in "The On-Line Encyclopedia
of Integer Sequences."