Contractible Edges in a 4-Connected Graph with Vertices of Degree Greater Than Four

摘要

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. Let G be a 4-connected graph which has a vertex x with degree greater than four. We show that if the subgraph induced by N G (x)∩ V 4(G) is not isomorphic to the path of length three, then there are at least two 4-contractible edges whose distance from x is one or less, where N G (x) and V 4(G) stand for the neighborhood of x and the set of vertices of G whose degree is 4, respectively. We also show that G has at least |V ≥ 5(G)| 4-contractible edges.