# Sparsest cut is solvable on trees

The problem is to prove that Sparsest cut is solvable on trees in polynomial time.

A short review, a sparsest cut is linear program

$$\min \frac{c(S,\overline{S})}{D(S,\overline{S})}$$

where $c(S,\overline{S})$ - sum of edge weights for every edge that crosses the cut $S,\overline{S}$

and $D(S,\overline{S})$ - sum of demands between $s_{i}$ and $t_{i}$ are separated by $S,\overline{S}$

The proof is based on the claim.

There exists a sparsest cut $(S,\overline{S})$, such that the graphs $G[S]$ and $G[\overline{S}]$ are connected.

Proof of the claim:

Without loss of generality, assume $G[S]$ is not connected. Say it has components $C_{1}...C_{t}$. Let the total capacity of edges from $C_{i}$ to $\overline{C}_{i}$ be $c_{i}$ and the demand be $d_{i}$. The sparsity of cut $S$ is $\frac{c_{1}+\cdots+c_{t}}{d_{1}+\cdots+d_{t}}$. Now since all quantities $C_{i},d_{i}$ are non-negative, by simple arithmetic, there exists $i$ such that $\frac{c_{i}}{d_{i}} \leq \frac{c_{1}+\cdots+c_{t}}{d_{1}+\cdots+d_{t}}$. This implies that cut $C_{i}$ is at least as good as $S$.

Using this claim we know that the sparsest cut on trees will be exactly one edge. Therefore, the sparsest cut problem on trees becomes easy to solve in polynomial time.

The problem is I don't really understand how the claim was proved. I think it was proved by contradiction, firstly we assumed that $G[S]$ is not connected and found a better that $(S,\overline{S})$ cut for a component $C_{i}$, which is contradiction therefore $S$ is connected. Am I wrong? Secondly, how does this claim apply that sparsest cut is solvable on a tree. Just because as a component $C_{1}$ we can take a one edge of the tree? And how to show that it's solvable in polynomial time?

Thanks!

-