Битва при Мелитене
- 1 year ago
- 0
- 0
Лемма Кёнига о бесконечном пути — теорема , которая даёт достаточное условие на существование бесконечного пути в графе . Эта теорема играет важную роль как пример в конструктивной математике и теории доказательств .
Доказана Денешем Кёнигом в 1927 году .
Пусть — бесконечный , но локально конечный (то есть каждая его вершина имеет конечную степень ) связный граф . Тогда содержит бесконечный простой путь , то есть путь без повторяющихся вершин, который начинается в одной вершине и продолжается бесконечно долго.