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.
Alternative interpretation of graph-minor theorem
1
$\begingroup$
graph-theory
1 Answers
1
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.
-
0Sorry 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. – 2012-11-01