The New Lower Bound Of The Number Of Vertices Of Degree 5 And Trivially Noncontractible Edges In Contraction Critical 5 Connected Graphs

An edge of a k connected graph is said to be k contractible if the contraction of this edge resultsin a k connected graph. It is known that every 3 connected graph of order 5 or more contains a 3contractible edge. By using this fact, in 1980, Thomassen([1]) proved three Kuratowski's theoremsabout planar graph by induction. So, the existence of k contractible edges in a k connected graphplays an vital role in proving some properties of a graph by induction. From then on, a lot of studyof k contractible edges in k connected graph have been down(J2] [3] [4][5]). If G does not have any kcontractible edge, then G is called contractible critical k connected. In order to get some conditionsof having a contractible edge in a k connected graph, it is natural to study the contraction criticalk connected graph.Egawa([6]) proved that every contraction critical k connected graph has a fragment withcardinality at most k/4. So, for k=4, 5, 6, 7, every contraction critical k connected graph contains avertex of degree k. It is known that there are not contraction critical 3 connected graphs of order 5or more([7]), and there are only two special classes for contraction critical 4 connected graph: thesquare of a cycle or the line graph of a cyclically 4 connected 3 regular graph([8][9]). Then it isnatural to study the structure of contraction critical 5 connected graph, this problem appears verydifficult, and also attracted many people's attention. In order to study the structure of contractioncritical 5 connected graph, we firstly try to study some properties of contraction critical 5 connectedgraph. From the result of Egawa we have known that every contraction critical 5 connected graphhas at least a vertex of degree 5. For the distribution of vertices of degree 5 in contraction critical5 connected graph, in 1994, Yuan Xudong obtained that:Theorem A([10]) Let G be a contraction critical 5 connected graph. Then any vertex of Gis adjacent to a vertex of degree 5.By Theorem A, we can deduce that any contraction critical 5 connected graph G has at least1/5|G| vertices of degree 5. Later Sudianji improved Theorem A by:Theorem B([11]) Let G be a contraction critical 5 connected graph. Then any vertex of Gis adjacent to two vertex of degree 5.By Theorem B, we can deduce that any contraction critical 5 connected graph G has at least2/5|G| vertices of degree 5. Recently QinCheng fu proved that:Theorem C([12]) Let G be a contraction critical 5 connected graph. Then |V₅(G)|≥4/9|V(G)|. In this paper, we obtain the further result:Theorem 1 Let G be a contraction critical 5 connected graph. Then G has at least 1/2|G|vertices of degree 5.For contraction critical k connected graph G, Thomassen([1]) proved that G has a triangle,later Mader([13]) proved that G has at least 1/3|G| triangles. Recently, Kriesell([14]) proved thatG contains at least 2/3|G| triangles. As contraction critical 5 connected graph has lots of trianglesand vertices of degree 5, it also has lots of triangles through vertices of degree 5. An edge of a kconnected graph is said to be trivially noncontractible if its end vertices have a common neighborof degree k. Ando proved that:Theorem D([15]) Each contraction critical 5 connected graph of order n has at least n/2trivially noncontractible edges.And he put forward the following conjecture:Conjecture Each contraction critical 5 connected graph of order n has at least 2n triviallynoncontractible edges.Recently, LiXiangjun proved that:Theorem E([16]) Any contraction critical 5 connected graph G has at least |G|+1 triviallynoncontractible edges.By using Theorem E, here we obtain the further result:Theorem 2 Let G be a contraction critical 5 connected graph. Then G has at least 3/2|G|trivially noncontractible edges.