An exact lower bound on the number of cut‐sets in multigraphs

A cut‐set in an undirected multigraph G is a subset of edges whose removal makes the graph disconnected. Let m i (G) denote the number of all cut‐sets, each of which consists of i edges. In this paper, for any multigraph G with n nodes and e (⩾3n/2) edges, we show that m i (G) with α ⩽ i ⩽ 2(α ‐ γ) ‐ 3, where α = ⌊2e/n⌋ and γ = ⌊2e/n(n ‐ 1) ⌋, is greater than or equal to ( \documentclass{article}\pagestyle{empty}\begin{document}$ \left({\matrix{ {e - \alpha } \cr {i - \alpha } \cr } } \right) $\end{document} )((α + 1)n ‐ 2 e ) + ( \documentclass{article}\pagestyle{empty}\begin{document}$ \matrix{ {e - \alpha - 1} \cr {i - \alpha - 1} \cr } $\end{document} )(2 e ‐ αn ). A necessary and sufficient condition for a multigraph G with given n and e to minimize m i (G) for an i with i ⩽ 2(α ‐ γ) ‐ 3 is presented. We also show that there exists a graph such that the lower bound is tight for all i in the range [α, 2(α ‐ γ) ‐ 3]. © 1994 by John Wiley & Sons, Inc.