A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs

An edge of a kk-connected graph is said to be kk-contractible if its contraction results in a kk-connected graph. A kk-connected non-complete graph with no kk-contractible edge, is called contraction critical kk-connected. An edge of a kk-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree kk. 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 nn vertices has at least n/2n/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+1n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on nn vertices has at least 32n trivially noncontractible edges.