WikiSort.ru - Не сортированное

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

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

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

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

Примечания