Let $n$ be the number of vertices in $V$. We can assume that $G$ has the following two properties: (i) $|E| \leq 2n-1$, and (ii) $G$ is 2-vertex connected. Assumption (i) is based on the fact that any extreme point of $LP(G)$ has at most $2n-1$ edges (see Theorem 4.9 in [@cornuejols1985traveling]), and restricting the graph to the edges in the support of an extreme point with optimal value does not increase the optimal value $OPT_{LP}(G)$. Assumption (ii) is based on Lemma 2.1 from [@DBLP:conf/focs/MomkeS11]. We note that the two theorems we just cited may have to be applied multiple times to guarantee that $G$ has the desired properties (i) and (ii).

\[lem:xisone\] Let $G=(V,E)$ be a 2-edge connected graph. Then there exists $x \in
LP(G),~ x \leq 1$ minimizing the sum of coordinates of a vector in $LP(G)$.

Let $x \in LP(G)$ be an extreme point that minimizes the sum of coordinates of a vector in $LP(G)$. Suppose that there is some $x_e >
1$ for $e \in E$. Since $G$ is 2-edge connected, each cut crossing edge $e$ must include at least one other edge. Suppose that $x_e$ does not belong to any tight cuts, i.e. $x(\delta(S)) > 