In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered (under homeomorphic embedding). The theorem was conjectured by Andrew Vázsonyi and proved by Joseph Kruskal (1960); a short proof was given by Nash-Williams (1963).
Higman's lemma is a special case of this theorem, of which there are many generalizations involving trees with a planar embedding, infinite trees, and so on. A generalization from trees to arbitrary graphs is given by the Robertson–Seymour theorem.
Read more about Kruskal's Tree Theorem: Friedman's Finite Form
Famous quotes containing the words tree and/or theorem:
“On a tree by a river a little tom-tit Sang “Willow, titwillow, titwillow!”
And I said to him, “Dicky-bird, why do you sit Singing, “Willow, titwillow, titwillow!””
—Sir William Schwenck Gilbert (1836–1911)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)