The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds
Robert E. Bixby · Networks · 1975
The problem studied is the following: What is the minimum number of edges and vertices in a graph with edge connectivity n and exactly m n‐bonds (cuts)? It is perhaps surprising that this problem turns out to have an essentially closed form solution for all m and n (Theorem C at the end of Section 5). Furthermore, the methods employed make it possible, for many values of m and n, to actually write down a graph that achieves the minimum. These methods involve, as an interesting by‐product, estimating the solutions of integer minimization problems of the form where k varies as part of the minimization. In particular, it is shown that the obvious “greedy” algorithm (i.e., choose r 0 as large as possible, then r 1 as large as possible and so forth until m is exhausted) almost works.