Лема Кеніга

Лема Кеніга про нескінченний шлях — теорема, яка дає достатню умову існування нескінченного шляху в графі. Ця теорема відіграє важливу роль як приклад у конструктивній математиці і теорії доведень.

Довів Денеш Кеніг 1927 року^[1].

Формулювання

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

Зауваження

Корисним окремим випадком цього твердження є те, що кожне нескінченне дерево містить вершину нескінченного степеня або нескінченний простий шлях.

Джерела

Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)

Примітки

↑ Kőnig, D. (1927), «Über eine Schlussweise aus dem Endlichen ins Unendliche», Acta Sci. Math. (Szeged) (3(2-3)): 121—130.

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.

[1] Kőnig, D. (1927), «Über eine Schlussweise aus dem Endlichen ins Unendliche», Acta Sci. Math. (Szeged) (3(2-3)): 121—130.

[1]