Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.
Statement of the lemma Let G {\displaystyle G} be a connected, locally finite, infinite graph. This means that every two vertices can be connected by a finite path, each vertex is adjacent to only finitely many other vertices, and the graph has infinitely many vertices. Then G {\displaystyle G} contains a ray: a simple path (a path with no repeated vertices) that starts at one vertex and continues from it through infinitely many vertices. Another way of stating the theorem is: "If the human race never dies out, somebody now living has a line of descendants that will never die out". A useful special case of the lemma is that every infinite tree contains a vertex of infinite degree or an infinite simple path. If it is locally finite, it meets the conditions of the lemma and has a ray, and if it is not locally finite then it has an infinite-degree vertex.
Construction The construction of a ray, in a graph G {\displaystyle G} that meets the conditions of the lemma, can be performed step by step, maintaining at each step a finite path that can be extended to reach infinitely many vertices (not necessarily all along the same path as each other). To begin this process, start with any single vertex v 1 {\displaystyle v_{1}} . This vertex can be thought of as a path of length zero, consisting of one vertex and no edges. By the assumptions of the lemma, each of the infinitely many vertices of G {\displaystyle G} can be reached by a simple path that starts from v 1 {\displaystyle v_{1}} . Next, as long as the current path ends at some vertex v i {\displaystyle v_{i}} , consider the infinitely many vertices that can be reached by simple paths that extend the current path, and for each of these vertices construct a simple path to it that extends the current path. There are infinitely many of these extended paths, each of which connects from v i {\displaystyle v_{i}} to one of its neighbors, but v i {\displaystyle v_{i}} has only finitely many neighbors. Therefore, it follows by a form of the pigeonhole principle that at least one of these neighbors is used as the next step on infinitely many of these extended paths. Let v i + 1 {\displaystyle v_{i+1}} be such a neighbor, and extend the current path by one edge, the edge from v i {\displaystyle v_{i}} to v i + 1 {\displaystyle v_{i+1}} . This extension preserves the property that infinitely many vertices can be reached by simple paths that extend the current path. Repeating this process for extending the path produces an infinite sequence of finite simple paths, each extending the previous path in the sequence by one more edge. The union of all of these paths is the ray whose existence was promised by the lemma.
… excerpt ends here. Continue reading the full article.
