The Number of Removable Edges in 3-Connected Graphs

An edge of a 3-connected graphGis said to be removable ifG−eis a subdivision of a 3-connected graph. Holtonet al.(1990) proved that every 3-connected graph of order at least five has at least ⌈(|G|+10)/6⌉ removable edges. In this paper, we prove that every 3-connected graph of order at least five, except the wheelsW5andW6, has at least (3 |G|+18)/7 removable edges. We also characterize the graphs with (3 |G|+18)/7 removable edges.