Лемма Кёнига о бесконечном пути
(перенаправлено с «Лемма Кёнига о бесконечном дереве»)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Denes_K%C3%B6nig_-_%C3%9Cber_eine_Schlussweise_aus_dem_Endlichen_ins_Unendliche.png/220px-Denes_K%C3%B6nig_-_%C3%9Cber_eine_Schlussweise_aus_dem_Endlichen_ins_Unendliche.png)
Лемма Кёнига о бесконечном пути — теорема, которая даёт достаточное условие на существование бесконечного пути в графе. Эта теорема играет важную роль как пример в конструктивной математике и теории доказательств.
Доказана Денешем Кёнигом в 1927 году[1].
Формулировка
[править | править код]Пусть — бесконечный, но локально конечный (то есть каждая его вершина имеет конечную степень) связный граф. Тогда содержит бесконечный простой путь, то есть путь без повторяющихся вершин, который начинается в одной вершине и продолжается бесконечно долго.
Замечания
[править | править код]- Полезным частным случаем этого утверждения является то, что каждое бесконечное дерево содержит вершину бесконечной степени или бесконечный простой путь.
Примечания
[править | править код]- ↑ Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Math. (Szeged) (3(2-3)): 121–130.