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   {\displaystyle G\ } n   {\displaystyle n\ } csúcsú egyszerű gráf fokszámai nagyság szerint d 1 ≤ d 2 ≤ . . . ≤ d n {\displaystyle d_{1}\leq d_{2}\leq ...\leq d_{n}} . Ha minden k < n 2 {\displaystyle k<{\frac {n}{2}}} -re d k ≥ k + 1 {\displaystyle d_{k}\geq k+1} teljesül, akkor G   {\displaystyle 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
  • Matematika Matematikaportál • összefoglaló, színes tartalomajánló lap
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!