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!