no. 14 · Friday 13 November 2026
Sharp Bounds on the Number of Small Cuts
Abstract
A $k$-cut of an undirected graph is a minimal edge set whose removal leaves at least $k$ connected components, and its cost is the sum of its edge costs. Write $λ_k$ for the minimum cost of a $k$-cut. For fixed $k\ge2$ and $α\ge1$, we show that in any $n$-vertex graph with $n\ge k$ and nonnegative edge costs, the number of $k$-cuts of cost strictly below $αλ_k$ is $O(n^{\lceilαk\rceil-1})$. This implies an $O(n^{\lfloorαk\rfloor})$ bound for $k$-cuts of cost at most $αλ_k$, sharpening the $O(n^{αk})$ bound of Gupta, Harris, Lee and Li. For $k=2$, our strict bound resolves a conjecture of Henzinger and Williamson and an open question of Karger. The exponent $\lceilαk\rceil-1$ is optimal for $k$-cuts for every $k\ge2$ and $α>1$.
- fields
- Combinatorics