Contractible Subgraphs Of Quasi 5-connected Graphs

The construction of connected graph plays an important role in graph theory and its application,and the research on graph with low-order connectivity has obtained a lot of important results.The contractible subgraphs of graph with certain connectivity is an important tool for discussing the structure of these graphs,and,when the con-tractible subgraph is known,we can generate these graphs in turn.In this paper,we try to focus on how to generate quasi 5-connected graphs.We put forward the definition of contraction critical quasi 5-connected graph and try to find the technics of how to discuss two cuts,with k vertices and k+1 vertices respectively,at the same time.Then we try to find out the contractible subgraphs of some special quasi 5-connected graphs,especially for the number of contractible edges and the local structure of contraction critical quasi 5-connected graphs.The main conclusions are as follows:(1)Let G be a bowtie free quasi 5-connected graph and x be a vertex of G,we try to find the 4-contractible edge around x.Based on the local structure around every vertex of G,we show that |E4c(G)|≥|V(G)|+1/2|V5(G)|+1/2|V6(G)|+|V≥7(G)|;(2)It is shown that 3/2|V≥5(G)|,further,we show that this bond is as best as possible;(3)Let G be a quasi 5-connected graph and x be a vertex of G.If d(x)=4 and every vertex of N(x)∪ {x} incident with no contractible edge then G has a triangle xyz such that G/xyz is a quasi 5-connected graph;(4)Let G be a quasi 5-connected graph with no vertex of degree 4 contained in triangle.If d(x)=4 then x incident with at least one contractible edge;(5)Let G be a contraction critical minimal quasi 5-connected graph on at least 13 vertices then every cycle of G has vertex with degree at most 5.