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}\leq d_{2}\leq ... \leq d_{n}$. Ha minden $k<\frac{n}{2}$-re $d_{k}\geq k+1$ teljesül, akkor $G\$ -ben van Hamilton-kör.

Megjegyzés:

• Pósa-tétel $\Rightarrow$ Ore-tétel

Hivatkozások

• Katona─Recski─Szabó: A számítástudomány alapjai, Typotex, Budapest, 2003.