Removable Edges And Chords Of Longest Cycles In 4-Connected Graphs

In 1976, Thomassen conjectured that every longest cycle in 3-connected graph has a chord. The conjecture has been verified for several types of 3-connected graph. Moreover, the conjecture is extended to 4-connected graph. In this paper, we will verify the conjecture is true for a class of 4-connected graph that is described by removable edges. Next, we will show the main def-inition and theorem.Firstly, the definition of a removable edge as follows:Let G be a 4-connected graph,and an edge e in E(G). And removing e from G, we get a new graph, named G-e.(1)If the degree of all vertices in G-e is no less than 4,let G(?)e=G-e.(2)If there exist vertices whose degree is 3 in G-e, then remove them and join their three neighbors by a triangle unless they are already adjacent(so multiple can be avoided). And we denote the resultant graph G(?)e. An edge e of a 4-connected graph G is called removable if G(?)e is still 4-connected; otherwise e is called unremovable.Finally, the main theorem.Let G be a 4-connected graph and let C be a longest cycle of G. If|E(C) ∩ ER(G)|≤ 7, then C has a chord.