CONNECTIVITY, GRAPH MINORS, AND SUBGRAPH MULTIPLICITY

It is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three-con nected. We generalize these results to similarly characterize certain other minor-closed families of graphs; in particular, G occurs O(n) ti mes as a subgraph of the K(b,c)-free graphs, b greater-than-or-equal-t o c and c less-than-or-equal-to 4, iff G is c-connected. Our results u se a simple Ramsey-theoretic lemma that may be of independent interest .