Königovo lemma na nekonečné cestě

Koenigovo lemma nekonečné cesty je věta , která dává dostatečnou podmínku pro existenci nekonečné cesty v grafu . Tato věta hraje důležitou roli jako příklad v konstruktivní matematice a teorii důkazů .

Prokázáno Deneschem Königem v roce 1927 [1] .

Formulace

Dovolit být nekonečný, ale lokálně konečný (to znamená, že každý jeho vrchol má konečný stupeň ) připojený graf . Pak obsahuje nekonečnou jednoduchou cestu , tedy cestu bez opakujících se vrcholů, která začíná v jednom vrcholu a pokračuje donekonečna.

Poznámky

• Užitečným speciálním případem tohoto tvrzení je, že každý nekonečný strom obsahuje vrchol nekonečného stupně nebo nekonečnou jednoduchou cestu .

Poznámky

1. ↑ Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Matematika. (Szeged) (3(2-3)): 121–130.