If every graph component has at most vertices, assigning whole graph components to two sides gives an empty graph cut with the displayed bound. To prove it, maximize the smaller side's weight . If , every component on the larger side has weight at least , because moving a smaller one would improve the smaller side. There are at least such components, since their total exceeds times the permitted maximum weight. Thus , a contradiction. The proof also works for arbitrary positive weights.
Articles by others on the same topic
There are currently no matching articles.