A graph G with n nodes and e edges maximizing the edge-connectivity λ (i.e., satisfying λ(G)=⌊2e/n⌋) has been obtained by Harary in 1962. Recently, the problem for finding a graph G with λ(G)=⌊2e/n⌋ which minimizes the number of cut-sets with ⌊2e/n⌋ edges has been solved. Such graphs play an important role in analysis and maximization of the network reliability subject to arc failures. In this paper, the authors present a necessary and sufficient condition for a graph to minimize the number of cut-sets with x edges, where x=2 or x•2⌊2e/n⌋-3. As a result, it is shown that a graph minimizing the number of cut-sets with the order x(¸•2⌊2e/n⌋-3) also minimizes the number of cut-sets with the order less than x. [In Japanese.]
