Pósa-tétel

A Pósa-tétel Pósa Lajos 1962-es gráfelméleti tétele, mely így szól: Legyenek $G$ $n$ csúcsú egyszerű gráf fokszámai nagyság szerint $d_1\le d_2\le ...\le d_n$. Ha minden $k<\frac{n}{2}$-re $d_k\ge k+1$ teljesül, akkor $G$-ben van Hamilton-kör.

A Pósa-tételből következik az Ore-tétel.

Források

• Katona–Recski–Szabó: A számítástudomány alapjai, Typotex, Budapest, 2003.
• A Pósa-tételről bővebben
• A Pósa-tétel a MathWorld-ön
• A Pósa-tétel általánosítása