The structure of quasi 4-connected graphs

Abstract A minimal 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. This paper provides the following structural characterization of quasi 4-connected graphs. Every quasi 4-connected graph can be obtained from a wheel on at most six points, or a prism or a Mobius ladder by repeatedly (i) adding edges, (ii) splitting points, and/or (iii) replacing a triangle containing points of degree at least four by the graph obtained from K 4 by deleting an edge.