The number of removable edges in a 4-connected graph

Let <f>G</f> be a 4-connected graph. For an edge <f>e</f> of <f>G</f>, we do the following operations on <f>G</f>: first, delete the edge <f>e</f> from <f>G</f>, resulting the graph <f>G-e</f>; second, for all the vertices <f>x</f> of degree 3 in <f>G-e</f>, delete <f>x</f> from <f>G-e</f> and then completely connect the 3 neighbors of <f>x</f> by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by <f>G⊖e</f>. If <f>G⊖e</f> is still 4-connected, then <f>e</f> is called a removable edge of <f>G</f>. In this paper we prove that every 4-connected graph of order at least six (excluding the 2-cyclic graph of order six) has at least <f>(4|G|+16)/7</f> removable edges. We also give the structural characterization of 4-connected graphs for which the lower bound is sharp. [Copyright &y& Elsevier]