The Contraction Edges In The K-connected Graphs

The study of the structure of graphs is an important field in graph theory.It is the base of graph theory and has a great influence on the development of graph theory.The contractible edge is a powerful tool for studying the structure of connected graphs and plays an important role in the inductive proving of graph properties.In this paper,we focus on the contractible subgraphs of k-connected graphs.The main results are as follows:Let G be a 3-connected graph and H be a spanning tree of G.If E?H????E_N?G?then G is called a fox.We concern the local structure of fox.We show that if d?x?=3 then x is incident to exactly one non-contractible edge.It is proved that the number of non-contractible edges in a minimal fox is |V?G?|-1,that is,there is only one spanning tree H such that E?H????E_N?G?.We give the lower bound for the number of vertices of degree 3,that is|V₃?G?|?V?G?+1/2.Further,we find a subgraph H'around the special subgraph H such that,G/H'is a fox.This offer a possible way to give an inductive constructing of fox.Let G is 3-connected graph,H be a spanning tree of G.If |E?H????E_N?G?|-2 then G is called a quasi-fox.It is shown that quasi-fox has possible six kinds of local structure.Base on this,we show that if the root of the DFS tree H of the 3-connected graph G is not 3-degree vertex then H contains at least two contractible edges of G.There are examples show that this result is as best as possible.Finally,we study the local structure of maximal critical k-connected graphs.We show that every maximal critical k-connected graph contains an edge e such that G/e is a critical k-connected graph.