The New Lower Bound Of The Number Of Vertices Of Degree 6 In Contraction Critical 6 Connected Graphs

For a vertex set F(?)V(G), we write N_G(F)=(U_x∈FN_G(x))-F. Let G be a noncomplete graph and T a smallest separating set, F is the union of the vertices of at least one but not of all the components of G-T then F is called a fragment of G or a T-fragment. Let (?)=V(G)-T-F, then(?)≠φand it is also a T-fragment. We call F and (?) are two fragments of graph G which is separated by T. If F is a fragment, but any proper subset of F is not a fragment of G, then F is called a end of G, and a fragment with minimum number of vertices is called an atom. In order to convertions we often omit the different of V(F) and F. x∈V(G), let E(x) denote the set of edges incident to x. Let F is a fragment of graph G, x∈V(G), then F is called an E(x)-fragment if N(F) contains the two endvertices of some edge which included in E(x).An edge of a k connected graph G is said to be k contractible edge, or simply contractible edge, if its contraction results still in a k connected graph. In 1961 Tutte[15] proved that any 3 connected graph with order at least 5 has 3 contractible edges. After that, the contractible edges in 3 connected graph has been studied extensively. As for the distribution and the lower bound of the number of contractible edges in 3 connected graph, we refer the reader to[4]. For k≥4, Thomassen[14] showed that there are infinitely many k connected k regular graphs, which do not have a contractible edge. A noncomplete k connectecd graph is called contraction critical k connectecd if G has no k contractible edge. In order to get some conditons of having a contractible edge in a k connnected graph, it is natural to study the contraction critical k connectecd graph. For k=4, Martinov[12] completely characterized all contraction critical 4 connected graph, that is: There are only two special classes for 4 connected graph without 4 contractible edge: the square of a cycle or the line graph of a cyclically 4 connected 3 regular graph.For k≥5, it is very difficult to give a characteration to the contraction critical k connected graph. However, Egawa[5] proved that every contraction critical k connected(k≥4) graph has a fragment with cardinality at most k/4, from that we know that every contraction critical k connected (k≥4) graph has a vertex of degree at most「(5k)/4」-1. So, for 5≤k≤7, every contraction critical k connected graph contains a vertex of degree k. in resently, People has done a lot of work about the distribution and the lower bound of vertices of degree k in contraction critical k connected graph[2].Let V_k denote the set of vertices of degree k in G. Recently Ando et al asked the following problem:problem Let k be an integer such that 5≤k≤7. is there a constant c_k such that |V_k|≥c_k|V(G)| holds for a contraction -critical k connected graphG?, Moreoer, if there exists a such c_k, determine the largest value of c_k.For contraction critical 5 connected graph, in 1994, YuanXudong obtained that: any vertex of contraction critical 5 connected graph is adjacent to a vertex of degree 5. From this we can deduce that any contraction critical 5 connected graph G has at least 1/5|G| vertices of degree 5. In 1997, SuJianji obtained that: any vertex of contraction critical 5 connected graph is adjacent to two vertex of degree 5. From this we can deduce that any contraction critical 5 connected graph G has at least 2/5|G| vertices of degree 5. in 2003, Ando obtained the result which Yuan had obtained in 1994. Recently QinChengfu improved the result by that: let G be a contraction critical 5 connected graph, then |V₅(G)|≥4/9|V(G)|.For k=6, Yuan and Su[20] proved that:Theorem A Any contraction critical 6 connected graph has a pair of adjacent vertices of degree 6.QiEnfeng, YuanXudong obtain the furter result:Theorem B For each vertex x of degree 6 in a contraction critical 6 connected graph, either there is a neighbor of degree 6 of x, or there exists a vertex y in N(x) such that there are two adjacent vertices of degree 6 in the neighborhood of y.For contraction critical 6 connected graph, Ando et al[1] obtained that:Theorem C Let G be a contraction critical 6 connected graph and H=[V₆(G)]. Then, for each x∈W, there is a E(x)-fragment A of cardinality two such that either(1)H[N(A)∩V₆(G)](?)2K₂ or (2) W∩N(A)={x} and H[N(A)∩V₆(G)(?)K₂∪K₁.From Theorem C, they obtained that:Theorem D Let G be a contraction critical 6 connected graph, then it has at least 1/7|G| vertices of degree 6.In 2005, Zhaoqiaofeng and QiEnfeng improved this result by:Theorem E Let G be a contraction critical 6 connected graph, then it has at least 1/5|G| vertices of degree 6. In this paper, we obtain the further result by improved Theorem E:Theorem 1 Let G be a contraction critical 6 connected graph, then it has at least 1/4|G| vertices of degree 6.