On the purity of minor-closed classes of graphs

© 2018 Elsevier Inc. Given a graph H with at least one edge, let gapH(n) denote the maximum difference between the numbers of edges in two n-vertex edge-maximal graphs with no minor H. We show that for exactly four connected graphs H (with at least two vertices), the class of graphs with no minor H is pure, that is, gapH(n)=0 for all n⩾1; and for each connected graph H (with at least two vertices) we have the dichotomy that either gapH(n)=O(1) or gapH(n)=Θ(n). Further, if H is 2-connected and does not yield a pure class, then there is a constant c>0 such that gapH(n)∼cn. We also give some partial results when H is not connected or when there are two or more excluded minors.