Generating Internally Four-Connected Graphs

AbstractA graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges. A graph G is internally 4-connected if it is simple, 3-connected, has at least five vertices, and if for every partition (A, B) of the edge-set of G, either |A|⩽3 or |B|⩽3 or at least four vertices of G are incident with an edge in A and an edge in B. We prove that if H and G are internally 4-connected graphs such that they are not isomorphic, H is a minor of G, and they do not belong to a family of exceptional graphs, then there exists a graph H′ such that H′ is isomorphic to a minor of G and either H′ is obtained from H by splitting a vertex or H′ is an internally 4-connected graph obtained from H by means of one of four possible constructions. This is a first step toward a more comprehensive theorem along the same lines