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-connected. We generalize these results to similarly characterize certain other minor-closed families of graphs; in particular, G occurs O(n) times as a subgraph of the K_b,c-free graphs, b ≥ c and c ≤ 4, iff G is c-connected. Our results use a simple Ramsey-theoretic lemma that may be of independent interest. © 1993 John Wiley & Sons, Inc.