Finite rooted trees are well-quasi-ordered by rooted-tree homeomorphic embedding. Consequently every infinite sequence contains an earlier tree embedding into a later one. Size-controlled finite forms follow by applying König infinity lemma to the finitely branching tree of bad prefixes.
Finite rooted trees labelled in a well-quasi-ordering are a well-quasi-ordering under label-monotone tree embedding. A minimal bad sequence argument makes the collection of proper rooted subtrees a well-quasi-ordering; Higman lemma then compares their child lists while the root labels are compared in the label order.
For every natural parameter , there is a finite length such that every sequence of finite rooted trees satisfying has an earlier tree homeomorphically embedding into a later tree. It is a true finite-combinatorial principle unprovable in Peano arithmetic and in arithmetical transfinite recursion theory. Each fixed-parameter instance can still be verified by a sufficiently large finite search.
Articles by others on the same topic
Kruskal's tree theorem is a result in graph theory and combinatorics that deals with the structure of trees and their embeddings within each other. More specifically, it provides criteria for the comparison and embedding of trees.