Editing Kőnig's lemma (section)

==Statement of the lemma==
Let <math>G</math> be a [[connected graph|connected]], [[Glossary of graph theory terms#finite|locally finite]], [[Glossary of graph theory terms#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 <math>G</math> contains a [[Ray (graph theory)|ray]]: a [[path (graph theory)|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".<ref>{{harvtxt|Knuth|1968}}, p.&nbsp;382</ref>

A useful special case of the lemma is that every infinite [[tree (graph theory)|tree]] contains either a vertex of infinite [[degree (graph theory)|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 <math>G</math> 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 <math>v_1</math>. 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 <math>G</math> can be reached by a simple path that starts from <math>v_1</math>.

Next, as long as the current path ends at some vertex <math>v_i</math>, 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 <math>v_i</math> to one of its neighbors, but <math>v_i</math> 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 <math>v_{i+1}</math> be such a neighbor, and extend the current path by one edge, the edge from <math>v_i</math> to <math>v_{i+1}</math>. 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.