A Hamilton-connected graph 
is a graph in which every two distinct
vertices are connected by a Hamiltonian
path (Bondy and Murty 1976, p. 61). In other words, it has a 
Hamiltonian path for
all pairs of distinct vertices 
and 
. The illustration above shows a set
of Hamiltonian paths that make the wheel
graph 
hamilton-connected.
By definition, a graph with vertex count 
having a detour matrix whose off-diagonal elements
are all equal to 
is Hamilton-connected. Conversely, any graph
having a detour matrix with an off-diagonal element
less than 
is not Hamilton-connected.
Every Hamilton-connected graph on at least three vertices is Hamiltonian. Every complete
graph is Hamilton-connected. A bipartite graph
on at least three vertices is not Hamilton-connected;
is Hamilton-connected but is not Hamiltonian.
Every Hamilton-connected graph on at least four vertices has vertex connectivity at least 3. Indeed, deleting one or two chosen vertices from a Hamiltonian path having the chosen vertices among its endpoints leaves a path spanning all remaining vertices. Consequently, a graph on at least four vertices with vertex connectivity less than 3 cannot be Hamilton-connected.
Dupuis and Wagon (2015) conjectured that all non-bipartite Hamiltonian vertex-transitive
graphs are Hamilton-connected except for odd cycle
graphs 
with 
and the dodecahedral graph (Dupuis and Wagon
2015; Gregor et al. 2024, p. 35:2).
A simple algorithm for determining if a graph is Hamilton-connected proceeds as follows. For each pair 
of distinct vertices,
start with the original graph:
1. Add a new vertex 
.
2. Add new edges 
and 
.
3. If this graph is not Hamiltonian, return false; otherwise, continue to next pair.
If the algorithm checks all pairs without returning false, return true.
For a graph 
on 
vertices, the strong
closure of 
is the graph obtained by repeatedly adding an edge
between nonadjacent vertices 
and 
whenever their vertex degrees
satisfy 
,
stopping when no such pair remains. The graph 
is Hamilton-connected iff its strong
closure is Hamilton-connected (Wong 1997). In particular, if the strong closure is
a complete graph, then 
is Hamilton-connected.
A small modification of a theorem due to Chvátal and Erdős establishes that if 
for a graph 
, where 
is the independence
number and 
the vertex connectivity,
then 
is Hamilton-connected (A. E. Brouwer, pers. comm., Dec. 17, 2012).
As a result of the theorem that for a connected regular graph 
on 
vertices with vertex
degree 
and smallest graph eigenvalue 
,
 |
it therefore follows that if
 |
for a connected regular graph, the graph is Hamilton-connected (A. E. Brouwer, pers. comm., Dec. 17, 2012).
Every 8-connected claw-free graph is Hamilton-connected (Hu et al. 2005), as is every Johnson graph (Alspach 2013). Chen and Quimpo (1981) proved that a connected Cayley graph on a finite Abelian group of odd order with vertex degree at least three is Hamilton-connected.
The locally twisted cube graphs 
are Hamilton-connected for 
(Ma and Xu 2006). This distinguishes them from the corresponding
hypercube graphs 
, which are bipartite.
Pensaert (2002) conjectured that for 
with 
, the generalized
Petersen graph 
is Hamilton-laceable if 
is even and 
is odd, and Hamilton-connected otherwise.
The numbers of Hamilton-connected simple graphs on 
,
2, ... nodes are 1, 1, 1, 1, 3, 13, 116, ... (OEIS
A057865), the first few of which are illustrated
above.
Examples of Hamilton-connected graphs include antiprism graphs, complete graphs, Möbius
ladders 
for even 
,
prism graphs 
for odd 
, wheel graphs, the truncated
prism graph, truncated cubical graph, truncated tetrahedral graph, Grötzsch
graph, Frucht graph, and Hoffman-Singleton
graph.
