Removable Edges in Longest Cycles of 4-Connected Graphs

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 the graph G–e; second, for all vertices x of degree 3 in G–e, delete x from G–e 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 Ge. If Ge is 4-connected, then e is called a removable edge of G. In this paper we obtain some results on removable edges in a longest cycle of a 4-connected graph G. We also show that for a 4-connected graph G of minimum degree at least 5 or girth at least 4, any edge of G is removable or contractible.Acknowledgment. The authors are greatly indebted to a referee for his valuable suggestions and comments, which are very helpful to improve the proof of our main result Lemma 3.3.Research supported by National Science Foundation of China AMS subject classification (2000): 05C40, 05C38, 05C75Final version received: March 10, 2004