Lemma 37 — infinite path in a finitely branching rooted tree
ProvedSymmetricPSM1041.ORLowerBound.konig_infinite_rooted_treecombinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an infinite rooted tree with vertex set and root . Assume that every vertex has a finite set of children. Then there is a sequence such that
Thus the tree has an infinite path starting at the root. Leaves are permitted; infinitude does not assert that each vertex extends. This is the compactness ingredient used by the source's finite Higman derivation.
Differences from the source:
- encoding: a rooted tree and an infinite path from its root → a reachable parent-map tree and an injective child sequence beginning at the root; reason: every rooted tree has the parent representation; the root’s self-parent is excluded from child edges
Preamble
import Mathlib import Definitions.Def_SymmetricPSM1041_ORLowerBound_RootedTree
Formal statement
namespace SymmetricPSM1041.ORLowerBound
theorem konig_infinite_rooted_tree {V : Type*} [Infinite V] (T : RootedTree V)
(hfinite : ∀ v, (children T v).Finite) :
∃ p : ℕ → V, p 0 = T.root ∧ Function.Injective p ∧
∀ k, p (k + 1) ∈ children T (p k) := by sorry
end SymmetricPSM1041.ORLowerBound
Source
Marshall Ball, Peter Crawford-Kahrl, Vladimir Podolskii, Morgan Prior, STOC 2027 submission #1041 (October 2026), p. 26, Lemma 37
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.