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.