Editing Robertson–Seymour theorem (section)

==Statement==
A [[minor (graph theory)|minor]] of an [[undirected graph]] <math>G</math> is any graph that may be obtained from <math>G</math> by a sequence of zero or more [[Edge contraction|contractions]] of edges of <math>G</math> and deletions of edges and vertices of <math>G</math>. The minor relationship forms a [[partial order]] on the set of all distinct finite undirected graphs, as it obeys the three axioms of partial orders: it is [[Reflexive relation|reflexive]] (every graph is a minor of itself), [[Transitive relation|transitive]] (a minor of a minor of <math>G</math> is itself a minor of <math>G</math>), and [[Antisymmetric relation|antisymmetric]] (if two graphs <math>G</math> and <math>G</math> are minors of each other, then they must be [[graph isomorphism|isomorphic]]). However, if graphs that are isomorphic may nonetheless be considered as distinct objects, then the minor ordering on graphs forms a [[preorder]], a relation that is reflexive and transitive but not necessarily antisymmetric.<ref>E.g., see {{harvtxt|Bienstock|Langston|1995}}, Section 2, "well-quasi-orders".</ref>

A preorder is said to form a [[well-quasi-ordering]] if it contains neither an [[infinite descending chain]] nor an infinite [[antichain]].<ref>{{harvtxt|Diestel|2005|p=334}}.</ref> For instance, the usual ordering on the non-negative integers is a well-quasi-ordering, but the same ordering on the set of all integers is not, because it contains the infinite descending chain 0,&nbsp;&minus;1,&nbsp;&minus;2,&nbsp;&minus;3... Another example is the set of positive integers ordered by [[divisibility]], which has no infinite descending chains, but where the [[prime number]]s constitute an infinite antichain.

The Robertson–Seymour theorem states that finite undirected graphs and graph minors form a well-quasi-ordering. The graph minor relationship does not contain any infinite descending chain, because each contraction or deletion reduces the number of edges and vertices of the graph (a non-negative integer).<ref name="l05-78"/> The nontrivial part of the theorem is that there are no infinite antichains, infinite sets of graphs that are all unrelated to each other by the minor ordering. If <math>\mathcal{S}</math> is a set of graphs, and <math>\mathcal{M}</math> is a subset of <math>\mathcal{S}</math> containing one representative graph for each [[equivalence class]] of [[minimal element]]s (graphs that belong to <math>\mathcal{S}</math> but for which no proper minor belongs to <math>\mathcal{S}</math>), then <math>\mathcal{M}</math> forms an antichain; therefore, an equivalent way of stating the theorem is that, in any infinite set <math>\mathcal{S}</math> of graphs, there must be only a finite number of non-isomorphic minimal elements.

Another equivalent form of the theorem is that, in any infinite set <math>\mathcal{S}</math> of graphs, there must be a pair of graphs one of which is a minor of the other.<ref name="l05-78">{{harvtxt|Lovász|2005|p=78}}.</ref> The statement that every infinite set has finitely many minimal elements implies this form of the theorem, for if there are only finitely many minimal elements, then each of the remaining graphs must belong to a pair of this type with one of the minimal elements. And in the other direction, this form of the theorem implies the statement that there can be no infinite antichains, because an infinite antichain is a set that does not contain any pair related by the minor relation.