基本概念
汉密尔顿通路：给定图G，若存在一条经过图中的每个顶点一次且仅一次的通路，则称这条通路为汉密尔顿通路。
哈密尔顿回路：若存在一条回路，经过图中的每个顶点一次且仅一次，则称这条回路为汉密尔顿回路。
汉密尔顿图：具有汉密尔顿回路的图称为汉密尔顿图。
相关定理
定理1：若无相连通图G(V,E)具有汉密尔顿回路，则对于顶点集合V的人已非空子集S，均有W(G-S)<=|S|成立。其中|S|表示集合S中边的数目，W(G-S)表示G-S中连通分量的数目。
但是注意，用定理1来证明某一个特定图是非汉密尔顿图，这个方法并不是总是有效的，比如彼得森图符合定理1但是属于非汉密尔顿图。
定理2：设G是具有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n-1，则在G中存在一条汉密尔顿回路。
定理3：设G是具有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n，则在G中存在一条汉密尔顿回路。
注意：定理2和定理3是充分关系。
