2\cdot x(E(A,B))  + E(B,S) \label{eq:new}\\ && + ~ E(A,
\bar{S}\setminus{A \cup B}) + E(A,S) + E(B, \bar{S}\setminus{A \cup
  B}).\nonumber\end{aligned}$$ Since both of these cuts are tight and since $x_e > 1$ and $x_e \in
E(S, \bar{S}\setminus{A \cup B})$, it follows that: $$\begin{aligned}
x(\delta(S\cup A)) + x(\delta(S\cup B)) - 2\cdot x(E(S,
\bar{S}\setminus{A\cup B})) & < & 2.\end{aligned}$$ By , this implies that: $$\begin{aligned}
2\cdot x(E(A,B)) +  E(B,S)  +  E(A, \bar{S}\setminus{A \cup B}) +
E(A,S) + E(B, \bar{S}\setminus{A \cup B}) ~ < ~ 2. \label{eq:new2}\end{aligned}$$ However, if we consider the cut $E(A\cup B, ~V\setminus{A\cup B})$, we know that $x(E(A\cup B, ~V\setminus{A\cup B})) \geq 2$. $$\begin{aligned}
x(E(A\cup B, V\setminus{A \cup B})) & = & x(E(A,S)) + x(E(A,
\bar{S}\setminus{A \cup B})) + x(E(B,S)) \label{eq:new3} \\ && +~
x(E(B, \bar{S}\setminus{A \cup B}) ).\nonumber\end{aligned}$$ Since the quantity in is at most the quantity on the lefthand side of , it must be strictly less than 2, which is a contradiction. Therefore, we can conclude that the edge $x_e$ occurs in at most one tight cut, a case that we addressed above.

Applying Lemma \[lem:xisone\], we define $x \in {\mathbb R}^{|E|}$ to be an optimal solution for $LP(G)$ with the following properties: (i) the support of $x$ 