König Lemmája a végtelen ösvényen

A Koenig-féle végtelen út lemma egy olyan tétel , amely elégséges feltételt ad egy végtelen út létezéséhez egy gráfban . Ez a tétel fontos szerepet játszik példaként a konstruktív matematikában és a bizonyítási elméletben .

Denesch König 1927-ben bizonyította [1] .

Megfogalmazás

Legyen egy végtelen , de lokálisan véges (azaz minden csúcsának véges foka van ) összefüggő gráf . Azután egy végtelen egyszerű útvonalat tartalmaz , azaz egy olyan útvonalat, amely nem ismétlődő csúcsok, és amely egy csúcsnál kezdődik és határozatlan ideig tart.

Jegyzetek

• Ennek az állításnak egy hasznos speciális esete, hogy minden végtelen fa tartalmaz egy végtelen fokú csúcsot vagy egy végtelen egyszerű utat .

Jegyzetek

1. ↑ Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Math. (Szeged) (3(2-3)): 121–130.