Removable Edges in a 5-Connected Graph

摘要

An edge e of a k-connected graph G is said to be a removable edge if G e is still k-connected,where G e denotes the graph obtained from G by deleting e to get G θ e,and for any end vertex of e with degree k - 1 in G θ e,say x,delete x,and then add edges between any pair of non-adjacent vertices in N Gθe (x).The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1,11,14,15].In the present paper,we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph.Based on the properties,we proved that for a 5-connected graph G of order at least 10,if the edge-vertex-atom of G contains at least three vertices,then G has at least (3|G| + 2)/2 removable edges.