Optimal graphs with a cut vertex and given edge connectivity | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 70. DOI: 10.17223/20710410/70/4

The vertex connectivity k is the smallest number of vertices whose removal leads to a disconnected or trivial graph. The edge connectivity λ of a nontrivial graph is the smallest number of edges whose removal leads to a disconnected graph. D. Fulkerson and L. Shapley solved the problem of determining the minimum number of edges in a graph with a given number of vertices n and a given edge connectivity λ. In this paper, we study the minimal n-vertex graphs with given values of vertex and edge connectivity. The main result is that we determine the minimum number of edges that n-vertex graphs with an articulation point and a given edge connectivity λ >1 can have: [(λn + λ + 1)/2]. A scheme for constructing graphs with such a number of edges is proposed. This is always possible for n ≥ 2λ.