Lema lui König pe calea infinită

Lema de cale infinită a lui Koenig este o teoremă care oferă o condiție suficientă pentru existența unei căi infinite într-un grafic . Această teoremă joacă un rol important ca exemplu în matematica constructivă și teoria demonstrației .

Dovedit de Denesch König în 1927 [1] .

Formulare

Fie un graf conex infinit , dar local finit (adică fiecare dintre vârfurile sale are un grad finit ) . Apoi conține o cale infinită simplă , adică o cale fără vârfuri repetate care începe la un vârf și continuă la infinit.

Note

• Un caz special util al acestei afirmații este că fiecare arbore infinit conține un vârf de grad infinit sau o cale infinită simplă .

Note

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