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:
“There is hardly an American male of my generation who has not at one time or another tried to master the victory cry of the great ape as it issued from the androgynous chest of Johnny Weissmuller, to the accompaniment of thousands of arms and legs snapping during attempts to swing from tree to tree in the backyards of the Republic.”
—Gore Vidal (b. 1925)
“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)