Lema de König sobre el camino infinito
El lema del camino infinito de Koenig es un teorema que da una condición suficiente para la existencia de un camino infinito en un gráfico . Este teorema juega un papel importante como ejemplo en las matemáticas constructivas y la teoría de la demostración .
Probado por Denesch König en 1927 [1] .
Redacción
Sea un grafo conexo infinito pero localmente finito (es decir, cada uno de sus vértices tiene un grado finito ) . Entonces contiene un camino simple infinito , es decir, un camino sin vértices repetidos que comienza en un vértice y continúa indefinidamente.
Notas
- Un caso especial útil de esta afirmación es que todo árbol infinito contiene un vértice de grado infinito, o un camino simple infinito .
Notas
- ↑ Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Matemáticas. (Szeged) (3(2-3)): 121–130.