A Hamilton-connected graph is a graph in which every two 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 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. All complete graphs on at least two vertices are 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).

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.

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.

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.