Removable Cycles in 2‐Connected Graphs of Minimum Degree at Least Four

A. M. Hobbs [2] conjectured that if G is a 2-connected simple graph in which each vertex has degree at least four, then G contains a cycle C such that G-E(C) is 2-connected. We shall prove a generalisation of this conjecture. THEOREM 1. Let G be a 2-connected simple graph of minimum degree k, where k ^ 4, and let e be an edge of G. Then G — e contains a cycle C of length at least k — 1, such that G — E(C) is 2-connected. The lower bound on the length of 'removable' cycles in Theorem 1 is essentially best possible since there exist 2-connected simple graphs of minimum degree k whose longest 'removable' cycle has length k + i. Moreover, for the special case k = 4, we can construct 2-connected, 4-regular simple graphs whose longest 'removable' cycle has length four. The following counterexample which was independently constructed by N. L. Robertson [2] and the present author, shows that Hobbs' conjecture, and hence Theorem 1, does not hold for graphs in general. Throughout this paper, let G be a simple graph. For H a subgraph of G, let V{H), E(H), and Ct(H) denote the set of vertices, edges, and cut vertices, respectively of H. Let B be a block of H. Define Int (B, H), the set of internal vertices of B in H, by Int (B, H) = V(B)\Ct(H). We shall say that B is an end block, pendant block, or isolated block of H if B contains at most one cut vertex, exactly one cut vertex, or no cut vertices, respectively, of H. For v e V(H) let d H {v) denote the degree of v in H. We first state two elementary results concerning the connectivity of G.