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

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

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

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

ФормулировкаПравить

Пусть $\mathrm{\Gamma <!--\; \Gamma \; -->}$$\Gamma$  — бесконечный, но локально конечный (то есть каждая его вершина имеет конечную степень) связный граф. Тогда $\mathrm{\Gamma <!--\; \Gamma \; -->}$$\Gamma$  содержит бесконечный простой путь, то есть путь без повторяющихся вершин, который начинается в одной вершине и продолжается бесконечно долго.

ЗамечанияПравить

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