# sparsest cut always has solution

Hi!

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.

Thanks!

-
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