Лемма Кёнига о бесконечном пути

Лемма Кёнига о бесконечном пути — теорема, которая даёт достаточное условие на существование бесконечного пути в графе. Эта теорема играет важную роль как пример в конструктивной математике и теории доказательства.

Статья Кёнига 1927 года

Доказана Денешем Кёнигом в 1927 году[1].

Формулировка

Пусть — бесконечный, но локально конечный (то есть каждая его вершина имеет конечную степень) связный граф. Тогда содержит бесконечный простой путь, то есть путь без повторяющихся вершин, который начинается в одной вершине и продолжается бесконечно долго.

Замечания
  • Полезным частным случаем этого утверждения является то, что каждое бесконечное дерево содержит вершину бесконечной степени или бесконечный простой путь.

Примечания
  1. Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Math. (Szeged) (3(2-3)): 121–130.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.