MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The theorem of Robertson-Seymour about graph minors says that there exists no infinite family of graphs such that none of them is a minor of another one.

Apparently, it came as a generalization of the Kruskal's theorem that states that there exists no infinite family of rooted ordered trees such that none is a minor of another one. Here, rooted ordered means that the tree has a root, and that the edges escaping from a vertex are ordered. In other words, the trees are assumed to be embedded in the plane, and the minor operation has to respect this embedding.

Here comes the question: is Robertson-Seymour theorem true for planar graphs, when we add the condition that the minor operation respects the embedding? (i.e. we not only ask $G_i$ to be a minor of $G_j$ as an abstract graph, but also as an embedded graph.)

It is not clear to me that this should be a direct corollary of the original theorem, because of the amount of possible embeddings into the plane for a given planar graph.

share|cite|improve this question
@Pierre Dehornoy: I thought that the conclusion of Robertson-Seymour theorem could be strengthened to "A certain graph $G_m$ occurs as a minor infinitely many times in a given infinite sequence" ($G_m$ would be one of the finitely many minimal elements of the sequence, with respect to the "minor" order). If my understanding is correct, then the answer to your question is positive since $G_m$ has only finitely many planar embeddings, up to isotopy, so one of them would be repeated (infinitely often). – Misha Mar 28 '12 at 16:16
I guess, my understanding of R-S theorem is correct: If a sequence of graphs were to contain infinitely many minimal elements $G_m$ then the new sequence of graphs $(G_m)$ would violate R-S theorem. – Misha Mar 28 '12 at 16:33
@ Misha: This looks almost convincing, but I do not understand the end of the argument. One of the embedding of $G_m$ appears infinitely offen, but how does it says that this particular embedding is the one that was given at the beginning, i.e. that corresponds to the given embedding of $G_m$? – Pierre Dehornoy Mar 28 '12 at 23:46
@Pierre Dehornoy: Pierre, sorry, you a right, this argument does not answer your question. – Misha Mar 29 '12 at 13:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.