Sharp Bounds on the Number of Small Cuts

Chao Xu, Mingdong Yang

Let $\lambda$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $\alpha >1$, we prove that there are $O(n^{\lceil 2\alpha \rceil -1})$ cuts of size strictly below $\alpha \lambda$.…