A new lower bound on the number of trivially noncontractible edges 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. An edge of a k -connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k . Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61–72] proved that a contraction critical 5-connected graph on n vertices has at least n / 2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n + 1 . In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least 3 2 n trivially noncontractible edges.