Donald Bren School of Information and Computer Sciences

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. Even more generally, G occurs O(n) times as a subgraph of the K_b,c free graphs, b >/= c, if and only if G is c-connected; G occurs O(n) times as a subgraph of the K_a-free graphs if and only if G is (a - 1)-connected. Our results use a simple Ramsey-theoretic lemma that may be of independent interest.