定義1： 經(jīng)過圖中每個(gè)頂點(diǎn)一次且僅一次的通路稱為哈密頓通路。存在哈密頓回路的圖稱為哈密頓圖。
定理1： 設(shè)無向圖G=是哈密頓圖，V1是V的任意的非空子集，
則
p(G-V1)<=|V1|
其中，p(G-V1)為從G中刪除V1(刪除V1中各頂點(diǎn)及關(guān)聯(lián)的邊)后所得到的圖的連通分支。
定理2： 設(shè)G是n(n>=3)階無向簡單圖，如果G中任何一對不相鄰的頂點(diǎn)度數(shù)之和都大于等于n,則G是哈密頓圖。
推論： 設(shè)G是n(n>=3)階無向簡單圖，如果G中任何一對不相鄰的頂點(diǎn)的度數(shù)之和都大于等于n，則G是哈密頓圖。
定理3： 在n(n>=2)階有向圖D=中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子圖Kn，則有向圖中存在哈密頓圖。
推論： n(n>=3)階有向完全圖為哈密頓圖
定理1： 設(shè)無向圖G=是哈密頓圖，V1是V的任意的非空子集，
則
p(G-V1)<=|V1|
其中，p(G-V1)為從G中刪除V1(刪除V1中各頂點(diǎn)及關(guān)聯(lián)的邊)后所得到的圖的連通分支。
定理2： 設(shè)G是n(n>=3)階無向簡單圖，如果G中任何一對不相鄰的頂點(diǎn)度數(shù)之和都大于等于n,則G是哈密頓圖。
推論： 設(shè)G是n(n>=3)階無向簡單圖，如果G中任何一對不相鄰的頂點(diǎn)的度數(shù)之和都大于等于n，則G是哈密頓圖。
定理3： 在n(n>=2)階有向圖D=中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子圖Kn，則有向圖中存在哈密頓圖。
推論： n(n>=3)階有向完全圖為哈密頓圖