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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Статья Кёнига 1927 года

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

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

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

[править | править код]

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

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

Примечания

[править | править код]
  1. Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Math. (Szeged) (3(2-3)): 121–130.