Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

I have read some paper claim about graph-minor theorem that "Another equivalent form of the theorem is that, in any infinite set S of graphs, there must be a pair of graphs one of which is a minor of the other." So does it mean that graphs considered are infinitely large? Because in many papers Seymour stresses that they are talking about finite graphs, this confuses me.

share|cite|improve this question

No, you are right: each of the graphs is finite. But you cannot have an infinite set of these (finite) graphs, without one being the minor of another.

This should be contrasted with another domain where you can compare objects: natural numbers with division. There you can have an infinite set such that none of them is divisible by another (prime numbers). So the "minor relation" in (finite!) graphs avoids this. See the wikipedia page on Well-quasi-ordering for related examples on the concept.

share|cite|improve this answer
Thanks. But I still don't completely understand. When you say infinite set of finite graphs, do you mean graphs with same topology, or graphs with same vertices? For example, there are only finite many graphs that I could draw for 4 vertices (and different topologies). – LieX Oct 29 '12 at 10:03
I mean arbitrary graphs, of any topology and size. If you collect any infinite number of them, there will be a pair such that one can be transformed into the other by deleting and contracting edges (i.e, applying the graph minor operations). You are of course right you cannot have unbounded numbers of graphs if you fix the size. – Hendrik Jan Oct 29 '12 at 12:17
Sorry again, so what is finite about this graph (of arbitrary size and topology ) that you are mentioning. From what I get is that they have countably-infinite vertices, because a set of countably finite vertices graph cant be infinite. But then it wont be proper to call these graphs as finite. – LieX Nov 1 '12 at 11:24

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.