ON THE STRUCTURE OF C_3-CRITICAL MINIMAL 6-CONNECTED GRAPHS

摘要

In this paper, C_3-critical minimal 6-connected graphs are studied; they are defined as 6-connected graphs, any subgraph of which obtained by edge deletion is not 6-connected and in which any clique on at most 3 vertices is contained in a 6-cutset. It is proved that more than 5/9 all vertices of such a graph have degree 6.