Königs Lemma på den oändliga vägen
Koenigs oändliga väglemma är ett teorem som ger ett tillräckligt villkor för att det ska finnas en oändlig väg i en graf . Denna sats spelar en viktig roll som exempel i konstruktiv matematik och bevisteori .
Bevisad av Denesch König 1927 [1] .
Formulering
Låta vara en oändlig men lokalt ändlig (det vill säga var och en av dess hörn har en ändlig grad ) ansluten graf . Innehåller sedan en oändlig enkel bana , det vill säga en bana utan upprepade hörn som börjar vid en vertex och fortsätter i det oändliga.
Anteckningar
- Ett användbart specialfall av detta påstående är att varje oändligt träd innehåller en vertex av oändlig grad, eller en oändlig enkel väg .
Anteckningar
- ↑ Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Matematik. (Szeged) (3(2-3)): 121–130.