通过图中所有顶点一次且仅一次的通路称为哈密顿通路.
通过图中所有顶点一次且仅一次的回路称为哈密顿回路.
具有哈密顿回路的图称为哈密顿图.
具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图.
推论:设 是半哈密顿图,则对于 的任意非空真子集 ,均有 .其中 为 的连通分支数.
完全图 中含 条边不重的哈密顿回路,且这 条边不重的哈密顿回路含 中的所有边.
完全图 中含 条边不重的哈密顿回路,从 中删除这 条边不重的哈密顿回路后所得图含 条互不相邻的边.
设 是 的无向简单图,若对于 中任意不相邻的顶点 ,均有 ,则 中存在哈密顿通路.
推论 1:设 是 的无向简单图,若对于 中任意不相邻的顶点 ,均有 ,则 中存在哈密顿回路,从而 为哈密顿图.
若 含 阶竞赛图作为子图,则 具有哈密顿通路.
强连通的竞赛图为哈密顿图.
若 含 阶强连通的竞赛图作为子图,则 具有哈密顿回路.