How many minor-closed graph families are there?

Question

Has anyone proved or disproved that there are a finite number of minor-closed graph families? If not, what is the general belief in the math community?

Alternately, is there another approach (not using minors) to classifying undirected graphs?

Answer 1

There are infinitely many minor-closed families. Really all you need for a minor-closed family is some graph property $P$ such that either $P$ or $\neg P$ is closed under taking minors. You can come up with any kind of silly property $P$ you want so long as it's a boolean property of graphs (for every graph $G$, either $G$ has property $P$ or $G$ does not have property $P$).

For a concrete example, consider the property of planarity that is closed under taking minors. Let $A_0$ be the family of all planar graphs. Consider next the graph property of apexness:

Def: Graph $G$ is apex if $\exists v \in \operatorname{V}(G)$ such that $G-v$ is planar.

Let $A_1$ be the family of all apex graphs and note that $A_1$ is closed under taking minors and that $A_0 \subset A_1$. It is then natural to define the property of 2-apexness:

Def: Graph $G$ is 2-apex if $\exists v_1,v_2 \in \operatorname{V}(G)$ such that $G-\{v_1,v_2\}$ is planar.

This family of graphs, call it $A_2$, is also minor-closed. Then we can define $n$-apexness similary for each $n\in \mathbb{N}$ creating a countable list of minor-closed families such that : $$ A_0 \subset A_1 \subset A_2 \subset \dotsb \subset A_n \subset \dotsb $$

---

As for your alternate approach to classifying undirected graphs, instead of graph minors, you could talk about homeomorphic subgraphs. In fact, Kuratowski's original theorem was in terms of homeomorphic subgraphs rather than graph minors:

Thm: A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ (i.e. a subgraph homeomorphic to $K_5$ or $K_{3,3}$).

If I remember correctly, it's a happy accident that the family of forbidden minors and the family of "minimal homeomorphic subgraphs" are the same for planarity. For other graph properties these two characterizations do not necessarily lead to the same set.

Answer 2

Let $\mathcal{F}_G$ be the family of graphs not containing a given graph $G$ as a minor. Then for any graph $G$, $\mathcal{F}_G$ is minor-closed, since if $H$ does not contain $G$ as a minor, any minor of $H$ does not contain $G$ as a minor either. Now since $\mathcal{F}_{K_n}$ contains all $K_i$ with $i<n$, and no others, each $\mathcal{F}_{K_n}$ is distinct, and there are infinitely many minor-closed families.

In fact, the Robertson-Seymour Theorem implies that any minor-closed family of graphs that is not the set of all graphs can be expressed as an intersection of finitely many such $\mathcal{F}_G$.

Incidentally, you mentioned another question in a comment as to whether the union of a finite number of minor-closed families could contain all graphs. The answer is no. Suppose $\cup_{i \leq k} \mathcal{F_i}$ is the set of all graphs, with each $\mathcal{F}_i$ minor-closed, and not the set of all graphs. Then by the Robertson Seymour Theorem, for all $i \leq k$, $\mathcal{F}_i = \cap_{j} \mathcal{F}_{G^i_j}$ for some set of graphs $\{G^i_j\}$. But $\displaystyle \cap_{j} \mathcal{F}_{G^i_j} \subseteq \mathcal{F}_{G^i_1}$, so $\cup_{i \leq k} \mathcal{F_{G^i_1}}$ is also the set of all graphs. Now consider the graph $H = \displaystyle \cup_{i \leq k} G^i_1$, the disjoint union of all $G^i_1$. This graph is not a member of any $\mathcal{F}_{G^i_1}$, a contradiction.