On the existence of critically n-connected graphs
Ferdinand Gliviak · Czech digital mathematics library · 1976
GLIVIAKThis paper deals with undirected, directed and mixed graphs, too.All graphs will be finite, without loops and multiple edges.The vertex-connectivity and the edge-connectivity of directed or mixed graphs will be used in the sense of the strong connectivity.Let G be a graph.Then we denote byIf G is directed, then OQ(U) denotes the set of vertices adjacent to u by an edge going from u and IG(U) denotes the set of vertices adjacent to u by an edge going to u.The definitions of the notions not presented here can be found in [8], for every vertex v of G. Analogously one can define X-edge-critical and X-vertex-critical graphs.One can see that every regular undirected graph of degree n > 2 and vertexconnectivity n is ^-edge, ^-vertex, A-edge and X-vertex critical.Analogously it can be verified that every directed regular graph of indegree and outdegree n > 2, vertex-connectivity and edge-connectivity n is K-edge, ^-vertex, A-edge and .4-vertexcritical.These four classes of critical undirected or directed graphs were studied in many papers, e. g. [1], [2], [4-7], [9-15].We shall prove the following theorem on the existence of critical graphs.