The New Lower Bound of the Number of Vertices of Degree 5 in Contraction Critical 5-Connected Graphs

摘要

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. Let G be a contraction critical 5-connected graph, in this paper we show that G has at least vertices of degree 5.