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:
“Everyone who enjoys supposes that the tree was concerned with the fruit, but it was really concerned with the seed.—In this lies the difference between all those who create and those who enjoy.”
—Friedrich Nietzsche (1844–1900)
“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)