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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.