幾乎哈密頓圖 -- 來自

關於“幾乎哈密頓”有幾種不同的定義在使用。

根據 Punnim et al. (2007) 的定義，幾乎哈密頓圖是指在個節點上，具有哈密頓數的圖。

根據 Sanders (1987) 的定義，具有個頂點的圖，如果每個個頂點的子集都包含在一個迴路中，則該圖是幾乎哈密頓圖。這個定義類似於極大非哈密頓圖的定義。

本文采用 Punnim et al. (2007) 的定義。此型別的幾乎哈密頓圖在 , 2, ... 個頂點上的數量分別為 0, 0, 1, 1, 7, 28, 257, 2933, ... (OEIS A185360)，其中前幾個示例如上所示。

由於樹的哈密頓數為，因此幾乎哈密頓樹滿足，得出。由於 3-路徑圖是三個節點上唯一的樹，因此它也是唯一的幾乎哈密頓樹。

次哈密頓圖是幾乎哈密頓圖。許多（甚至可能全部？）snark 圖都是幾乎哈密頓圖。

Punnim et al. (2007) 表明廣義 Petersen 圖是幾乎哈密頓圖，當且僅當且時成立。

Punnim et al. (2007) 證明了對於每個偶數階，都存在幾乎哈密頓三次圖。Petersen 圖是 10 個頂點上唯一幾乎哈密頓三次圖，Tietze 圖是 12 個頂點上唯一幾乎哈密頓三次圖 (Punnim et al. 2007)。Punnim et al. (2007) 證明了個頂點上的三次非哈密頓圖是幾乎哈密頓圖，當且僅當它 2-連通且包含長度為的環。下表總結了個頂點上缺少 -環，因此不是幾乎哈密頓圖的 2-連通三次非哈密頓圖的示例。