Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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.