Removable edges in a cycle of a 4-connected graph

Abstract: Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting in the graph ; second, for all the vertices x of degree 3 in , delete x from and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by . If is still 4-connected, then e is called a removable edge of G. In this paper, we investigate the problem on how many removable edges there are in a cycle of a 4-connected graph, and give examples to show that our results are in some sense the best possible. [Copyright &y& Elsevier]