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 3 n ‐ 4 edges, then the graph K − 1 , obtained from K 6 by deleting an edge, is a minor of G. (2) If G has at least 3 n ‐ 4 edges then either K − 6 or the graph obtained by pasting two disjoint copies of K 5 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.