n = 1 mod 4，（n-1）/ 2-regular？

Question

考慮一個n階的圖，其中n是1 mod 4（I.E.五邊形，nonagons等），並假設它是一個（n-1）/ 2-正則圖。另外（可選地）假設它和它的補碼是連接的。

這種類型的圖可以驗證爲哈密爾頓算子，如果是的話，證明將如何粗略去？

Answer 1

按礦石定理

A graph with n vertices (n ≥ 3) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n or greater

在你的情況，這是(n-1)/2正則圖。因此，不相鄰頂點的總和將爲(n-1)。

此外，您還可以使用TUTTE下面的定理（1956年）：

A 4-connected planar graph has a Hamiltonian cycle.

按我的看法，如果有一個4連平面圖上的所有頂點子圖給定圖，那麼哈密頓週期就會存在。