Skip to main content
Research
Information Processing Letters
Paper

On the number of small cuts in a graph

View publication

Abstract

We prove that in an undirected graph there are at most O(n2) cuts of size strictly less than 3/2 of the size of the minimum cut.

Related

View all publications