A graph 
is Hamilton-connected if every two vertices of 
are connected by a Hamiltonian
path (Bondy and Murty 1976, p. 61). In other words, a graph is Hamilton-connected
if it has a 
Hamiltonian path for all pairs of 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.
All Hamilton-connected graphs are Hamiltonian. All complete graphs are Hamilton-connected (with the trivial exception of the singleton graph), and all bipartite graphs are not Hamilton-connected.
Dupuis and Wagon (2014) conjectured that all non-bipartite Hamiltonian vertex-transitive
graphs are Hamilton-connected except for odd cycle
graphs 
with 
and the dodecahedral graph.
A simple algorithm for determining if a graph is Hamilton-connected proceeds as follows. For all pairs 
of vertices:
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.
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.
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, prism graphs of odd order, wheel graphs, the truncated prism graph, truncated cubical graph, truncated tetrahedral graph, Grötzsch graph, Frucht graph, and Hoffman-Singleton graph.
