Лемма Кёнига о бесконечном пути
(перенаправлено с «Лемма Кёнига о бесконечном дереве»)
Лемма Кёнига о бесконечном пути — теорема, которая даёт достаточное условие на существование бесконечного пути в графе. Эта теорема играет важную роль как пример в конструктивной математике и теории доказательств.
![](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.