如果图 
的每两个顶点都由一条哈密顿路径连接，则称图 
为哈密顿连通图（Bondy 和 Murty 1976，第 61 页）。换句话说，如果对于所有顶点对 
和 
，图都存在 
哈密顿路径，则该图是哈密顿连通的。上面的图示显示了一组哈密顿路径，这些路径使轮图 
成为哈密顿连通图。
根据定义，如果一个顶点数为 
的图的绕道矩阵的非对角线元素都等于 
，则该图是哈密顿连通的。相反，任何绕道矩阵的非对角线元素小于 
的图都不是哈密顿连通的。
所有哈密顿连通图都是哈密顿图。所有完全图都是哈密顿连通的（平凡图除外），并且所有二分图都不是哈密顿连通的。
Dupuis 和 Wagon (2014) 推测，除了奇圈图 
(
) 和十二面体图之外，所有非二分哈密顿顶点传递图都是哈密顿连通的。
确定图是否为哈密顿连通图的一个简单算法如下。对于所有顶点对 
1. 添加一个新顶点 
。
2. 添加新边 
和 
。
3. 如果这个图不是哈密顿图，则返回 false；否则，继续下一对。
如果算法检查完所有对都没有返回 false，则返回 true。
Chvátal 和 Erdős 定理的一个小修改确立了：如果对于图 
，
，其中 
是独立数，
是顶点连通度，则 
是哈密顿连通的（A. E. Brouwer，私人通讯，2012 年 12 月 17 日）。
根据定理，对于一个在 
个顶点上，顶点度为 
，最小图特征值为 
的连通正则图 
，
 |
因此得出，如果
 |
对于连通正则图，该图是哈密顿连通的（A. E. Brouwer，私人通讯，2012 年 12 月 17 日）。
每个 8-连通的无爪图都是哈密顿连通的（Hu 等人 2005），每个 Johnson 图也是如此（Alspach 2013）。Chen 和 Quimpo (1981) 证明，在阶数为奇数的有限阿贝尔群上，顶点度至少为 3 的连通 Cayley 图是哈密顿连通的。
Pensaert (2002) 推测，对于 
(
)，如果 
是偶数且 
是奇数，则广义 Petersen 图 
是汉密尔顿可编排的；否则是哈密顿连通的。
在 
, 2, ... 个节点上的哈密顿连通简单图的数量是 1, 1, 1, 1, 3, 13, 116, ... (OEIS A057865)，其中前几个如上图所示。
哈密顿连通图的例子包括反棱柱图、完全图、莫比乌斯阶梯、奇数阶棱柱图、轮图、截角棱柱图、截角立方体图、截角四面体图、格罗奇图、弗鲁奇图和霍夫曼-辛格尔顿图。
