Kőnig's lemma

Kőnig's lemma states that every infinite, finitely branching tree contains an infinite path. It connects unbounded finite structure with an infinite branch.

Finitely branching tree: A rooted tree in which every node has finitely many children. Finite branching ensures at least one child subtree remains infinite at each step.
Compactness theorem: A logical principle stating that a set of sentences is satisfiable if every finite subset is satisfiable. Tree-based proofs use the lemma to assemble compatible finite satisfactions into an infinite model.
Rooted tree: A tree with one distinguished vertex called the root. The lemma's path is commonly constructed by starting at a root and choosing successive children.
Dénes Kőnig: A Hungarian mathematician known for foundational work in graph theory. The lemma is named for Kőnig, whose work helped establish graph theory as a field.
Infinite path: A sequence of adjacent vertices extending indefinitely through a graph or tree. The lemma guarantees such a path through the tree.
Infinite Ramsey theory: The study of unavoidable patterns in sufficiently large or infinite combinatorial structures. Recursive selection of an infinite branch supports proofs of infinite homogeneous structure.
Branching factor: The number of immediate descendants or alternatives available at a node. The lemma requires each node's number of children to be finite, not uniformly bounded.
Theorie der endlichen und unendlichen Graphen: Dénes Kőnig's 1936 book on finite and infinite graphs. Kőnig's graph-theoretic treatment helped disseminate the result and its setting.
Infinite pigeonhole principle: If infinitely many objects are divided among finitely many classes, one class contains infinitely many objects. At each level, finite branching lets the proof retain a child with infinitely many descendants.
Büchi automaton: A finite-state automaton that accepts infinite words when designated states occur infinitely often. Its runs can be analyzed through finitely branching trees of finite execution prefixes.

Linked from 2 pages