# If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

My problem is mainly from this lecture notes on convex optimization here page4

Consider a s-t Minimum problem, on unweighted undirected graph $$G=(V,E)$$,we can formalize in following linear integer programming problem

\begin{equation*} \begin{aligned} & \underset{}{\text{minimine}} & & \sum_{u,v\in E}|x_u-x_v| \\ & \text{subject to} & & x_s =1 ,x_t=0 &x_v\in \left\{ 0，1\right\} \forall v \in V \end{aligned} \end{equation*}

then we can relax to:

\begin{aligned} & \underset{}{\text{minimine}} & & \sum_{u,v\in E}|x_u-x_v| \\ & \text{subject to} & & x_s -x_t =1 \end{aligned}

for $$0 \leq l \leq 1$$ we define $$S_l:= \left\{v|x_v \geq l\right\}$$ then we have $$\sum_{u,v\in E}|x_u-x_v| \geq\int^{1}_{0}|\delta_l(S_l)|dl$$ where $$\delta_l(S_l)$$ denotes the crossing edge in $$S_l$$

how to see this inequality ?

It's important to first understand how $$\delta(S_l)$$ changes. When $$l = 0$$, $$S_l$$ contains all vertices, and when $$l = 1$$, $$S_l$$ contains no vertices. In either case, there is no edge going between $$S_l$$ and $$\overline{S_l}$$, so $$\delta(S_l) = 0$$.
For values of $$l$$ between $$0$$ and $$1$$, $$\delta(S_l)$$ contains exactly the edges with one endpoint in $$S_l$$ and one endpoint in $$\overline{S_l}$$. In particular, if we define
$$f_{ij}(l) =\left\{ \begin{array}{ll} 1 & \mbox{if } l \mbox{ is between } x_i \mbox{ and } x_j \\ 0 & \mbox{otherwise.} \end{array} \right.$$
then we have $$|\delta(S_l)| = \sum_{(i, j) \in \delta(S_l)} 1 = \sum_{\substack{(i,j) \in E \\ i \in S_l \\ j \not\in S_l}} 1 = \sum_{(i, j) \in E} f_{ij}(l).$$
Now let's consider one particular edge, from $$u$$ to $$v$$. Because $$f_{uv}(\cdot)$$ is just $$0$$ everywhere except for on one interval where it takes on the value $$1$$, the value of $$\int_0^1 f_{uv}(l)\,\mathrm{d}l$$ is just the length of the interval on which $$f_{uv}(l) = 1$$, that is, $$|x_u - x_v|$$. So
$$\sum_{(u, v) \in E} |x_u - x_v| = \sum_{(u, v) \in E} \int_0^1 f_{uv}(l)\,\mathrm{d}l = \int_0^1 \sum_{(u, v) \in E} f_{uv}(l)\,\mathrm{d}l = \int_0^1 |\delta(S_l)|\,\mathrm{d}l.$$