Properties Of Contraction Critical 5-Connected Graphs

An edge of a k- connected graph is said to be k- contractible if the contraction ofthis edge results in a k- connected graph. It is known that every 3- connected graph oforder 5 or more contains a 3- contractible edge. By using this fact, in 1980,C.Thomassen ([13]) proved three Karatowski's theorems about planar graph byinduction. So, the existence of k- contractible edges in a k- connected graph plays avital role in proving some properties of a graph by induction. From then on, a lot ofstudy of k-contractible edges in k-connected graph has been done. If G does not haveany k- contractible edge, then G is called contraction critical k -connected. Also, thestudy of the k- connected graph and the contraction critical k- connected graph mayprovide a clue for solving some difficult problem. Note that the close relation betweenthe contraction and minors of graphs, a problem proposed by Hadwiger in 1943 maybe such one, this problem appears very difficult, and also attracted many people'sattention.Conjecture 1 (Hadwiger [3]) For an integer k (k≥1), any k- colorable graph has aKk ? minor. Up to now, very few results about it have been obtained. Dirac[25] proved thatany k minimal counterexamples to Hadwiger's conjecture is 5- connected fork≥5 . In 1947, Wagner ([14]) prove that the case of k=5 of conjecture 1 is equivalentto the Four Color Conjecture (Now Four Color Theorem). So for case k=5 ofHadwige conjecture is true. On the other hand, if one can prove the Hadwige'sconjecture for case k=5 directly, then there is another proof the Four Color Theoremwith only mathmatic technique. Hence, it is meaningful to study the construction ofminimal counterexamples of case k=5. Another interesting problem is about minorminimal 5- connected graphs. It is known that minors minimal of 3- connected graphsis K4 and of 4- connected are C6 and K5. As for 5- connected graph, it is still 2open and seems very difficult to determine it. M.Kriesell [24] conjecture thefollowing.Conjecture 2. Every 5- connected graph contains a minor, which is isomorphic toone of the graphs: K6, K2 is ,2,2,1,C5 ? K3, I, I~, or G0 . Where I is icosahedron, I~the graph obtained from I by replacing the edges of the cycle abcdea induced by IVthe neighborhood of some vertex with the edges of a cycle abceda , and G0 is thegraph obtained from the icosahedrom by deleting a vertex w with the two edgesac and ad , and finally, identifying b and e . Conjecture 2 is also open except for some special cases. For planar 5- connectedgraph, Dirac proved it has a minor isomorphic to icosahedron. G.FIJANZ recentlyproved that conjecture 2 hold for projective planar graphs. Also it is known thatcontraction critical 4- connected graphs are Cn and the line graph of cyclically 24-connected 3- regular graph. From this one can determine all minors minimal 4-connected graphs. In this paper, we study some properties of contraction critical 5-connected graphs (such as the distribution of vertices of degree 5 and triangles), andtry to characterize some structure of contraction-critical 5- connected graphs, and tryto find some results which are useful for determining minor-mininal 5- connectedgraph. For the contraction critical 5- connected graph, much less results are known.The following are some related results.Theorem A [15] Let G be a contraction critical 5- connected graph. Then any vertexof G is adjacent to a vertex of degree 5. Later Su Jianji improved Theorem A byTheorem B [12] Let G be a contraction critical 5- connected graph. Then any vertexof G is adjacent to two vertices of degree 5. By Theorem B, we can deduce that any 5- contraction critical graph has at least2 |V(G)| vertices of degree 5 . Here we study further the distributio...