$x$-value crossing this cut is at least 1 and all of the edges in this cut cover the cut.

A vertex $v \in T_{int}$ that is satisfied by $x$ is called [ *LP-satisfied*]{}.

A vertex $v \in T_{int}$ that is not satisfied by $x$ is called [ *LP-unsatisfied*]{}.

\[lem:expensive\] An expensive vertex is LP-satisfied.

An expensive vertex $v$ in $T_{int}$ has two incoming back edges. Since each vertex has maximum degree four, it may not have any outgoing back edges. Thus, the cut formed by removing the incoming tree edge is crossed by back edges that have $x$-value at least $1$ and these back edges also cover the tree cut obtained by removing the outgoing tree edge adjacent to $v$.

\[lem:heavy\] An LP-unsatisfied vertex is heavy.

If the vertex $v$ is a non-branch vertex, then consider the north cut and the south cut on vertex $v$. Each of these cuts has value greater than $1$, otherwise the cut would be LP-satisfied.

If the vertex is a branch vertex with three outgoing tree edges, it must be LP-satisfied. If it has two outgoing tree edges and one incoming back edge, then consider the tree cut obtained by removing the outgoing tree 