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

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

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

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

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

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

Замечания

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