2$ for all $S$ such that $e \in \delta(S)$. Then we can decrease the value of $x_e$ and obtain a smaller solution, which is a contradiction to the optimality of $x$.

Therefore, suppose that $e$ is in exactly one tight cut. Since there is at least one other edge besides $e$ crossing this cut and this edge must have value strictly less than 1, we can increase the $x$-value on this edge and decrease $x_e$. Since the cut is still tight, the solution is still feasible and has the same value as the original solution.

The other case to consider is when $e$ belongs to at least two tight cuts. Consider the cuts $(S+A,\bar{S}\setminus{A})$ and $(S + B,
\bar{S}\setminus{B})$, where $S, A,$ and $B$ are disjoint. Suppose that $e=ij$ and $i \in S$ and $j \in \bar{S}\setminus{A \cup B}$. Then edge $e$ crosses both these cuts. $$\begin{aligned}
\delta(S+ A) & = & E(S,\bar{S}\setminus{A \cup B}) + E(S,B) +  E(A, B)
+ E(A, \bar{S}\setminus{A \cup B}),\\
\delta(S+B) & = &  E(S,\bar{S}\setminus{A \cup B}) + E(S,A) + E(A,B) +
E(B, \bar{S}\setminus{A \cup B}).\end{aligned}$$ Then we have: $$\begin{aligned}
x(\delta(S \cup A)) + x(\delta(S \cup B)) & = & 2\cdot x(E(S,\bar{S}\setminus{A
  \cup B})) + 