The Contractible Edges In The Longest Circle Of7-connected Graphs And The Contractible Non-edges Of3-connected Graphs

In graph theory,the main research is the construction of the graphs,and the tools are to construct connected graphs.In order to construct graphs, we introduce some operations like contractible edges and contractible non-edges,and they are powerful tools to study the structures of connected graphs and to prove some properties of connected graphs by induction. In this paper,we have two conclusions:one is the contractible edges in the longest circle of7-connected graphs.and the conclusions are(1)Let P:x=x1x2...xn=y is the longest (x,;y)-path of G,xixi+1is an non-contractible edge,and S={xi,xi+1, u1, u2,u3,u4,u5} is the corresponding7-vertex cut,then there is at least one vertex of P in every component of G-S.(2)T is the minimum vertex cut of7-connected graph G.and the order of each fragment of G-T is bigger than3,then there is at least one contractible edge in the longest (x, y)-path. Based on the above results,we prove that(3) the order of each fragment of G-T is bigger than3,then there are at least two contractible edges in the longest circle of7-connected graphs. The other is that the contractible non-edges of constructed graphs Gv,graphs without triangles in3-connected graphs.And the conclusions are:(1)Gu is3-connected; Let (x,y) is any non-edge in Gu,then (x,y) is contractible if and only if (x,y) is contractible in G; In all Gt,s,any non-edge is non-contractiblc if and only if Gu is a wheel.(2)Let G does not contain triangles and G is not completed,T is the minimum cut of G,F is a fragment of T,then all non-edges between T and F are non-contractible.