On the Minimum Number of Vertices and Edges in a Graph with Prescribed Connectivities

The vertex connectivity $$k(G)$$ of a graph G is the minimum number of vertices whose removal results in a disconnected or trivial graph, that is, a graph with only one vertex. The edge connectivity λ(G) of a nontrivial graph G is the minimum number of edges whose removal results in a disconnected graph. It is known that the vertex connectivity $$k(G)$$ of a graph G , the edge connectivity λ(G) , and the minimum vertex degree δ(G) are related by the Whitney inequality k(G) ≤ λ(G) ≤ δ(G) . Previously, the authors solved the problem of finding the minimum number of vertices and edges in graphs with given $$k(G)$$ , λ(G) , and δ(G) . The present paper continues this study and essentially uses its results. Formulas for the minimum number of vertices and edges in graphs with given $$k(G)$$ and λ(G) are presented. Graphs with the minimum number of edges among all n -vertex graphs with given $$k(G)$$ and λ(G) are considered. A family of such graphs with λ n/2 edges is described. A special case of this family for k=λ is the Harary graphs Hk,n , that is, n -vertex k -connected graphs with the minimum number of edges. It is known that the number of edges in such graphs equals k n/2 . The result is also related to the problem of determining the minimum number of edges in an n -vertex graph with given λ(G) , which was solved by Fulkerson and Shapley.