How do I prove that the sparsest cut always has an optimal solution which is the cut for some vertex-subset?
It looks like it 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!