MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.

Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't remember something like this for multicut and multicommodity flow.

Can you give me a hint how to prove this.


share|cite|improve this question
What is a sparset cut? Did you mean sparsest cut? – Gilead Dec 10 '11 at 5:52
Thanks, corrected, of course sparsest cut – gosm Dec 10 '11 at 8:26
WHat does the question mean? What is "the cut for some vertex subset"? – Igor Rivin Dec 10 '11 at 15:48
I need to prove that there is always for any instance of the sparsest cut problem exists optimal solution which is cut $(S,\overline{S})$ for some vertex subset $S \subset V$ – gosm Dec 10 '11 at 19:45
As opposed to what? What other kind of cuts are there? – Igor Rivin Dec 11 '11 at 10:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.