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

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

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

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

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

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

Замечания

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

Примечания

  1. Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Math. (Szeged) (3(2-3)): 121–130.
Источник —

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