On minors of graphs with at least 3 n –4 edges

A point disconnecting set S of a graph G is a nontrivial m-separator, where m = |S|, if the connected components of G - S can be partitioned into two subgraphs, each of which has at least two points. A 3-connected graph is quasi 4-connected if it has no nontrivial 3-separators. Suppose G is a graph having n ≥ 6 points. We prove three results: (1) If G is quasi 4-connected with at least 3n - 4 edges, then the graph K−1, obtained from K6 by deleting an edge, is a minor of G. (2) If G has at least 3n - 4 edges then either K−6 or the graph obtained by pasting two disjoint copies of K5 together along a triangle is a minor of G. (3) If the minimum degree of G is at least 6, then K−6 is a minor of G. © 1993 John Wiley & Sons, Inc.