Pósa 定理

有几个与图的哈密顿圈相关的定理与 Pósa 相关。

设 是一个有 个图顶点的简单图。

1. 如果，对于每个 在 中，顶点度数不超过 的图顶点的数量少于 ，并且

2. 如果，对于 为奇数，顶点度数不超过 的图顶点的数量小于或等于 ，

那么 包含一个哈密顿圈。

Kronk (1969) 将此结果推广如下。设 是一个有 个图顶点的简单图，并设 。那么以下条件是 成为 -线哈密顿图的充分条件

1. 对于所有满足 的整数 ，顶点度数不超过 的图顶点的数量少于 ，

2. 度数不超过 的点的数量不超过 。

Pósa (1963) 推广了 Dirac 的一个结果，证明了每个有限简单图 ，其所有（或在某些情况下，几乎所有）顶点的度数都足够大，并且顶点数量足够多，则满足以下条件之一。

1. 有一条哈密顿线，包含给定不相交路径的所有边（定理 1），

2. 有一个顶点数量“大”的环路（定理 2 和 3），或

3. 有一个“小”数量的不相交环路，包含图的所有顶点（定理 4 和 5）。